2018 ICPC南京赛区网络赛

ACM-ICPC 2018 南京赛区网络预赛

A. An Olympian Math Problem

题意

$S=1×1!+2×2!+⋯+(n - 1) \times (n-1)!(n−1)×(n−1)!$问$Smodn$是多少。

题解

思维题,打表题?答案就是$n-1$证明如下。

看到$n-1$很不爽,那就加一个$(n-1)!$就凑好了。

$S+1!+2!+…+(n-1)!=2!+3!+…+n!$

之后再减掉。

$S=n!-1!$那么对$n$取余$S modn=-1modn=n-1$搞定。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T;
ll n;
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
printf("%lld\n",n-1);
}
return 0;
}

B. The writing on the wall

E. AC Challenge

题意

做题目,要按照一定顺序做题目,每个题目有两个值$a,b$,表示做了题目后增加$t*a+b$。

题解

状态压缩+剪枝+拓扑排序。

因为$n$的数据量小于$20$所以可以使用状态压缩。

$S$表示已经做的题目。

$vs$数组存储已知做题的最大值。如果做同样的题值比较小就减掉。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 30;
struct noddde{
int next,to;
}G[maxn*maxn*3];
int head[maxn],ind[maxn];
ll a[maxn],b[maxn];
int cnt;
void add(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
int n;
ll ans = 0;
ll vis[maxn];
ll vs[1<<22];
void dfs(int u,int t,ll temp,int S){
ans = max(ans,temp);
if(vs[S] > temp) return;
vs[S] = temp;
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
ind[v]--;
}
rep(i,1,n+1){
if(ind[i] == 0 && vis[i]==0){
vis[i] = 1;
dfs(i,t+1,temp+a[i]*t+b[i],S|(1<<i));
vis[i] = 0;
}
}
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
ind[v]++;
}
}
int main(){
#ifdef LOCAL
freopen("e.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d",&n);
rep(i,1,n+1){
int s;scanf("%lld%lld%d",&a[i],&b[i],&s);
rep(j,0,s){
int u;scanf("%d",&u);
add(u,i);ind[i]++;
}
}
rep(i,1,n+1){
if(ind[i]==0){
ind[i]++;
add(0,i);
}
}
ans = 0;
dfs(0,1,0,0);
printf("%lld\n",ans);
return 0;
}

G. Lpl and Energy-saving Lamps

题意

一个人去给所有房间换灯泡,每个月都会获得$m$个灯泡,每个房间有$a_i$个灯泡,之后以能换就换的态度每个月从第一个房间开始换,没有能换的房间就停止,把灯泡留到下一个月。换过灯泡就不用再换了。问给定月份中已经换好的房间数和当月剩下的灯泡数。

题解

线段树维护一个区间最小值。

由于线段树遍历是从前往后的,就不用担心顺序问题。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int day[maxn],remain[maxn];
int a[maxn],Min[maxn<<2],ask[maxn];
int n,m,now,ans;
void pushup(int rt){
Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
Min[rt] = a[l];
return;
}
int mid = (l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int l,int r,int rt){
if(Min[rt] > now) return;
if(l==r){
now -= Min[rt];
ans ++;
Min[rt] = INF;
return;
}
int mid = (l+r)>>1;
update(lson);
update(rson);
pushup(rt);
}
int main(){
#ifdef LOCAL
freopen("g.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,1,n+1) scanf("%d",a+i);
int maxq = 0;int q;
scanf("%d",&q);
rep(i,0,q){
scanf("%d",ask+i);
maxq = max(maxq,ask[i]);
}
build(1,n,1);
rep(i,1,maxq+1){
now += m;
update(1,n,1);
day[i] = ans;remain[i] = now;
}
rep(i,0,q){
printf("%d %d\n",day[ask[i]],remain[ask[i]]);
}

return 0;
}

I. Skr

题意

给定一个由数字构成的字符串,$n\leq 2000000$。问回文串加起来有多少?

题解

两种做法:

  1. 马拉车+hash
  2. 回文树+dfs

AC代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;
#define ULL unsigned long long
#define ll long long
const int maxn=4000000+40;
const int mod=1e9+7;
ULL P = 1313131;
ULL sqr[maxn/2],has[maxn/2],V[maxn];
ll ha[maxn/2],tmp[maxn/2];
int Laxt[maxn],Next[maxn],cnt=0;

const int MOD = 2000007;

bool _insert(ULL Now)
{
int u=Now%MOD;
for(int i=Laxt[u];i;i=Next[i]){
if(V[i]==Now) return true;
}
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
V[cnt]=Now;
return false;
}
ll ans=0;
void _hash(int x,int y){
ULL Now=has[y]-has[x-1]*sqr[y-x+1];
if(!_insert(Now))
{
ans+=((ha[y]-ha[x-1]*tmp[y-x+1]%mod)%mod+mod)%mod;
ans%=mod;
}
}
int r[maxn];
char c[maxn];
void _malacher()
{
int R=0,Mid=0,Len;

scanf("%s",c+1);
Len=strlen(c+1);
sqr[0]=tmp[0]=1;
has[0]=ha[0]=0;
for(int i=1;i<=Len;i++){
sqr[i]=sqr[i-1]*P;
has[i]=has[i-1]*P+c[i];
tmp[i]=tmp[i-1]*10%mod;
ha[i]=(ha[i-1]*10+c[i]-'0')%mod;
}

for(int i=1;i<=Len;++i) {
_hash(i,i);
if(R>i) r[i]=min(r[2*Mid-i],R-i);
while(i+r[i]+1<=Len&&c[i+r[i]+1]==c[i-r[i]-1]){
_hash(i-r[i]-1,i+r[i]+1);
r[i]++;
}
if(i+r[i]>R) {
R=i+r[i];
Mid=i;
}
}

cnt=0;Mid=0;R=0;
memset(Laxt,0,sizeof(Laxt));
memset(r,0,sizeof(r));
for(int i=2;i<=Len;++i) {
if(R>i) r[i]=min(r[2*Mid-i],R-i+1);
while(i+r[i]<=Len&&c[i+r[i]]==c[i-r[i]-1]) {
_hash(i-r[i]-1,i+r[i]);
++r[i];
}
if(i+r[i]-1>R) {
R=i+r[i]-1;
Mid=i;
}
}
printf("%lld\n",ans);
}
int main()
{
_malacher();
return 0;
}

AC代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
const int MAXN=2005005;
const ll MOD=1000000007ll;

ll pow(ll a,ll b){
ll t,y;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%MOD;
y=y*y%MOD; b=b>>1;
}
return t;
}

int len[MAXN];
int nxt[MAXN][15];
int fail[MAXN];
int num[MAXN];
int cnt[MAXN];
int last;
int S[MAXN];
int tot;
int N;

int new_node(int l){
cnt[tot]=0;
num[tot]=0;
len[tot]=l;
return tot++;
}

void init_tree(){
tot=0;
new_node(0);
new_node(-1);
last=0;
N=0;
S[N]=-1;
fail[0]=1;
}

int get_fail(int x){
while(S[N-len[x]-1]!=S[N])
x=fail[x];
return x;
}

void add_char(int c){
c-='0';
S[++N]=c;
int cur=get_fail(last);
if(!nxt[cur][c]){
int now=new_node(len[cur]+2);
fail[now]=nxt[get_fail(fail[cur])][c];
nxt[cur][c]=now;
num[now]=num[fail[now]]+1;
}
last=nxt[cur][c];
cnt[last]++;
}


ll jans=0;
ll oans=0;

void dfs1(int x,ll fa){
for(int i=1;i<=9;i++){
if(nxt[x][i]){
ll cur;
if(len[nxt[x][i]]==1){
jans+=i;
cur=i;
jans%=MOD;
}
else{
cur=i*pow(10,(len[nxt[x][i]]-1))%MOD+i+fa*10%MOD;
jans=(jans+cur%MOD)%MOD;
jans%=MOD;
}
dfs1(nxt[x][i],cur%MOD);
}
}
}

void dfs2(int x,ll fa){

for(int i=1;i<=9;i++){
if(nxt[x][i]){
ll cur;
cur=i*pow(10,(len[nxt[x][i]]-1))%MOD+i+fa*10%MOD;
oans=(oans+cur%MOD)%MOD;
dfs2(nxt[x][i],cur%MOD);
}
}
}


char str[MAXN];

int main(){
scanf("%s",str);
int N1 = strlen(str);
init_tree();
for(int i=0;i<N1;i++)
add_char(str[i]);
dfs1(1,0);
dfs2(0,0);
printf("%lld\n",(jans%MOD+oans%MOD)%MOD);
return 0;
}

L. Magical Girl Haze

题意

给定一个图,问从$1$走到$n$如果可以选择$k$条路为$0$,那么最短的路径是多少。

题解

分层图最短路+堆优化dijistra

每使用一次道路为0,就进入$step+1$的路径比较。比较好的dp思维。对于pair使用了一个小trick,负值就可以不用手写greater和重载小于了。但是现场赛应该还是手写node算了。

dp转移两种状态.

  • $dp[v][step+1] = min(dp[v][step+1],dp[u][step])$
  • $dp[v][step] = min(dp[v][step],dp[u][step]+val(u,v))$

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define mp make_pair
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int T,n,m,k,cnt;
struct node{
int to,next,val;
}G[maxn<<1];
int head[maxn];
ll dp[maxn][13],done[maxn][13];
void add(int u,int v,ll val){
G[cnt].to = v;
G[cnt].next = head[u];
G[cnt].val = val;
head[u] = cnt++;
}
void dijstra(){
priority_queue<pair<ll,pair<int,int> > > pq;
pq.push(mp(0,mp(1,0)));
dp[1][0] = 0;
while(!pq.empty()){
int u = pq.top().se.fi;
ll dis = pq.top().fi;
int step = pq.top().se.se;
pq.pop();
if(done[u][step]) continue;
done[u][step] = 1;
if(u == n){
printf("%lld\n",-dis);return;
}
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;ll val = G[i].val;
if(step<k && !done[v][step+1] && dp[v][step+1]<dis){
dp[v][step+1] = dis;
pq.push(mp(dis,mp(v,step+1)));
}
if(!done[v][step] && dp[v][step]<dis+val){
dp[v][step] = dis+val;
pq.push(mp(dp[v][step],mp(v,step)));
}
}
}
}
void init(){
memset(head,-1,sizeof(int)*(n+2));
cnt = 0;
memset(done,0,sizeof(done));
rep(i,1,n+1) rep(j,0,k+1) dp[i][j] = -1e16;
}
int main(){
#ifdef LOCAL
freopen("l.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
init();
rep(i,0,m){
int u,v;ll val;scanf("%d%d%lld",&u,&v,&val);
add(u,v,-val);
}
dijstra();
}
return 0;
}