头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2018 ICPC 南京站

传送门

$A.对称博弈,坑点是细节特别多。$


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
#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
scanf("%d %d",&n,&k);
if(n==0)
{
puts("Austin");
return 0;
}
if(k>=n)
{
puts("Adrien");
return 0;
}
if(k>=2)
{
puts("Adrien");
return 0;
}
if(k==1)
{
if(n&1)
puts("Adrien");
else
puts("Austin");
}
}

$J. 先做质因子分解,然后枚举每个质因子 \\
对答案的贡献 $


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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+5;
bool no_prime[maxn];
int minfac[maxn];
int prime[maxn/10],prime_;

void find_prime()
{
minfac[1]=1;
minfac[2]=2;
no_prime[1]=true;
int n=maxn;
for(int i=2; i<n; i++)
{
if(!no_prime[i])
{
prime[prime_++]=i;
minfac[i]=i;
}
for(int j=0; j<prime_&&prime[j]*i<n; j++)
{
no_prime[prime[j]*i]=true;
minfac[prime[j]*i]=prime[j];
if(i%prime[j]==0)
break;
}
}
}
int fac[100][2],fac_;
vector<int>v[maxn];//v[i] 代表
void getfac(int x)
{
fac_=0;
while(x!=1)
{
int little=minfac[x];
fac[fac_][0]=little;
fac[fac_][1]=0;
while(little!=1&&minfac[x]==little)
{
x/=little;
fac[fac_][1]++;
}
fac_++;
}
}

int n,a[maxn];

int main()
{
find_prime();
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n; i++)
{
//memset(fac,0,sizeof(fac));
getfac(a[i]);
for(int j=0; j<fac_; j++)
{
v[fac[j][0]].push_back(i);
}
}
ll ans=0;
for(int i=0; i<prime_; i++)
{
for(int j=0; j<v[prime[i]].size(); j++)
{
if(j==v[prime[i]].size()-1)
{
ans+=1ll*v[prime[i]][j]*(n-v[prime[i]][j]+1);
continue;
}
ans+=1ll*v[prime[i]][j]*(v[prime[i]][j+1]-v[prime[i]][j]);
}
}
printf("%lld\n",ans);
}
//1 5 9 10 2的贡献
//4+20+9+10=43 43+42+31=116

//1 6 7 10 3的贡献
//5+6+21+10=42
//3 4 5的贡献
//3+28=31
//2 =2 7的贡献

/*a1 a2 a3 ... ai a(i+1)
1 5 8
1*(4)=3 [1,1] [1,2]
5 (8-5)
*/

$I.建图跑最大流$


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
#include<bits/stdc++.h>
using namespace std;
const int eps=1e-12;
struct dinic
{
static const int maxn=2000;
static const int maxm=3e5;
static const int inf=1e9;
int cnt;
struct edge
{
int v,nex;
int c;
} g[maxm*2];
int lv[maxn],current[maxn],head[maxn];
void add_edge(int u,int v,int c)
{
g[cnt].v=v;
g[cnt].c=c;
g[cnt].nex=head[u];
head[u]=cnt++;

g[cnt].v=u;
g[cnt].c=0;
g[cnt].nex=head[v];
head[v]=cnt++;
}
void ini()
{
memset(head,-1,sizeof(head));
cnt=0;
}
void bfs(int s)
{
memset(lv,-1,sizeof(lv));
lv[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u]; ~i; i=g[i].nex)
{
edge &e=g[i];
if(e.c<=0||lv[e.v]>=0)
continue;
lv[e.v]=lv[u]+1;
q.push(e.v);
}
}
}
int dfs(int u,int t,int f)
{
if(u==t)
return f;
for(int &i=current[u]; ~i; i=g[i].nex)
{
edge &e=g[i],&rev=g[i^1];
if(e.c<=0||lv[u]>=lv[e.v])
continue;
int d=dfs(e.v,t,min(f,e.c));
if(d<=0)
continue;
e.c-=d;
rev.c+=d;
return d;
}
return 0;
}
int maxflow(int s,int t)
{
int flow=0;
while(1)
{
memmove(current,head,sizeof(head));
bfs(s);
if(lv[t]<0)
return flow;
int f;
while((f=dfs(s,t,inf))>0)
flow+=f;
}
}
} g;
int n,m,k;
int main()
{
scanf("%d %d %d",&n,&m,&k);
g.ini();
int t=n+m+1;
int s=n+m+2,a=n+m+3,b=n+m+4;
for(int i=1; i<=n; i++)
{
int ct;
scanf("%d",&ct);
for(int j=1; j<=ct; j++)
{
int x;
scanf("%d",&x);
g.add_edge(i,n+x,1);
}
}
for(int i=n+1; i<=n+m; i++)
g.add_edge(i,t,1);
for(int i=1; i<=n; i++)
g.add_edge(a,i,1),g.add_edge(b,i,1);
g.add_edge(s,a,1e9);
g.add_edge(s,b,k);
printf("%d\n",g.maxflow(s,t));
}

$G. 公式不太好推,先爆搜出前几项,然后 \\
连续做几次差分才能发现数列有规律。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll t,n;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
ll ans=n*(n+1)%mod*(n+2)%mod*(n+3)%mod*41666667%mod;
printf("%lld\n",ans);
}
}

$K.逗你玩,直接随机化输出答案,卡不住。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
char str[30];
int main()
{
srand(time(0));
int n,m;
char a[4]= {'U','D','L','R'};
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%s",str);
for(int i=1; i<=50000; i++)
printf("%c",a[rand()%4]);
printf("\n");
}

$D.最小球覆盖,几何法与模拟退火法两种做法,模拟退火的step要 \\
调大才能满足精度。$


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
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-14;
struct point3D
{
double x,y,z;
} data[105];
int n;
double dis(point3D a,point3D b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double solve()
{
double step=10000,ans=1e30,mt;
point3D z;
z.x=z.y=z.z=0;
int s=0;
while(step>eps)
{
for(int i=0; i<n; i++)
if(dis(z,data[s])<dis(z,data[i]))
s=i;
mt=dis(z,data[s]);
ans=min(ans,mt);
z.x+=(data[s].x-z.x)/mt*step;
z.y+=(data[s].y-z.y)/mt*step;
z.z+=(data[s].z-z.z)/mt*step;
step*=0.98;
}
return ans;
}
int main()
{
// freopen("t.txt","r",stdin);
double ans;
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%lf%lf%lf",&data[i].x,&data[i].y,&data[i].z);
ans=solve();
printf("%.15f\n",ans);

return 0;
}

$M.这份题解讲的很明白了,快速幂记得预处理,不然会T飞。$
传送门


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
114
115
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1e6+100;
const ll p=101;
const ll mod=1e9+7;
char s[maxn],t[maxn],str[maxn<<1];
ll hs[maxn],ht[maxn],hw[maxn<<1],pre[maxn];
ll len,qpow[maxn];
/*inline ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}*/
inline bool ok(ll mid,ll i,ll j)
{
ll h1=(hs[i]-hs[i-mid]*qpow[mid]%mod+mod)%mod;
ll h2=(ht[j]-ht[j-mid]*qpow[mid]%mod+mod)%mod;
return h1==h2;
}
inline void init()
{
str[1]='@';
str[2]='#';
for(ll i=1; i<=len; i++)
{
str[i*2+1]=s[i];
str[i*2+2]='#';
}
len=len*2+2;
}

inline void manacher()
{
ll maxright=0,mid;
for(ll i=1; i<=len; i++)
{
if(i<maxright)
hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
else
hw[i]=1;
for(; str[i+hw[i]]==str[i-hw[i]]; ++hw[i]);
if(hw[i]+i>maxright)
{
maxright=hw[i]+i;
mid=i;
}
}
}
int main()
{
scanf("%s",s+1);
scanf("%s",t+1);
ll len_s=strlen(s+1);
ll len_t=strlen(t+1);
qpow[0]=1;
for(int i=1;i<=min(len_s,len_t)+2;++i)
qpow[i]=qpow[i-1]*101%mod;
len=len_s;
for(ll i=1,j=len_t; i<j; i++,j--)
swap(t[i],t[j]);
hs[1]=s[1]-'a';
ht[1]=t[1]-'a';
for(ll i=1; i<=len_s; i++)
hs[i]=(hs[i-1]*p+s[i]-'a')%mod;
for(ll i=1; i<=len_t; i++)
ht[i]=(ht[i-1]*p+t[i]-'a')%mod;
init();
manacher();
for(ll i=1; i<=len; i++)
{
ll r=(hw[i]-1)/2;
if(!(i&1))
{
//@#a#a#
pre[i/2-r]++;
pre[i/2]--;
}
else
{
//@#a#b#a#
pre[(i-1)/2-r]++;
pre[(i-1)/2+1]--;
}
}
for(ll i=1; i<=len_s; i++)
pre[i]+=pre[i-1];
ll ans=0;
for(ll i=1; i<len_s; i++)
{
if(s[i]!=t[len_t])
continue;
ll l=0,r=min(i,len_t);
while(l+1<r)
{
ll mid=(l+r)/2;
if(ok(mid,i,len_t))
l=mid;
else
r=mid-1;
}
if(ok(l+1,i,len_t))
l++;
// cout<<l<<endl;
ans+=l*pre[i+1];
}
printf("%lld\n",ans);
}

未完待续。。。

avatar Decaku 如果人生的路有很长,愿你的荣耀永不退场。