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

2016 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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>v;
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res*=a;
a=a*a;
b>>=1;
}
return res;
}

void init()
{
v.clear();
for(int i=0; i<=30; i++)
{
for(int j=0; j<=30; j++)
{
for(int k=0; k<=30; k++)
{
for(int l=0; l<=30; l++)
{
ll tem=qpow(2,i);
if(tem>1e9) break;
tem*=qpow(3,j);
if(tem>1e9) break;
tem*=qpow(5,k);
if(tem>1e9) break;
tem*=qpow(7,l);
if(tem>1e9) break;
v.push_back(tem);
}
}
}
}
sort(v.begin(),v.end());
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
int x;
scanf("%d",&x);
printf("%d\n",*lower_bound(v.begin(),v.end(),x));
}
}

B:

$该级数收敛于 \pi^2/6,对1000万以下的询问预处理即可。$


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
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
double a[1000000+5];
string str;
int init(string s)
{
int res=0,len=s.length(),w=1;
for(int i=len-1;i>=0;i--)
{
res+=(s[i]-'0')*w;
w*=10;
}
return res;
}
void init()
{
for(int i=1;i<=1000000;i++)
{
a[i]=a[i-1]+1.0/(1.0*i*i);
}
}

int main()
{
init();
while(cin>>str)
{
if(str.length()>=7)
printf("%.5f\n",PI*PI/6);
else
{
int value=init(str);
printf("%.5f\n",a[value]);
}
}
}

E:

$当(n * (n-1)/2) \mod 2=0时游戏平衡 \\
所以n是偶数游戏就平衡。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int x;
scanf("%d",&x);
if(x&1) puts("Balanced");
else puts("Bad");
}
}

F:

$先判图是否连通。因为异或满足交换律,所以如果是欧拉通路 \\
答案是定值,如果是欧拉回路那就枚举起点,因为起点会被多 \\
算一次,否则答案都是NO。$


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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=5e5+5;
int t,n,m,u,v,ans;
int a[maxn],deg[maxn],cnt[maxn],f[maxn];

int Find(int a)
{
return f[a]==a?a:f[a]=Find(f[a]);
}
void join(int a,int b)
{
int pa=Find(a),pb=Find(b);
if(pa!=pb) f[pb]=pa;
}

void init()
{
for(int i=1; i<=n; i++)
{
f[i]=i;
deg[i]=cnt[i]=0;
}
}

int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
init();
ans=0;
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=m; i++)
{
scanf("%d %d",&u,&v);
deg[u]++;
deg[v]++;
join(u,v);
}
int _cnt=0;
for(int i=1; i<=n; i++)
{
cnt[i]=(deg[i]+1)/2;
if(f[i]==i) _cnt++;
}
if(_cnt!=1)
{
puts("Impossible");
continue;
}
_cnt=0;
for(int i=1; i<=n; i++)
{
if(deg[i]&1) _cnt++;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=cnt[i]; j++)
ans^=a[i];
}
if(_cnt==2)
{
printf("%d\n",ans);
continue;
}
if(_cnt==0)
{
int tem=ans;
ans^=a[1];
for(int i=2; i<=n; i++)
ans=max(ans,tem^a[i]);
printf("%d\n",ans);
continue;
}
puts("Impossible");
}
}

K:

$先跑spfa抠出最短路,然后在最短路上跑最大流即可。$


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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
const int maxm=1e4+5;
const int inf=1e9;
int cnt,s,t,n,m;
int head[maxn],dep[maxn],cur[maxn],dis[maxn],inq[maxn];
int g[maxn][maxn],e[maxn][maxn];
struct Edge
{
int nex,to,w;
} edge[2*maxm];

void add_edge(int u,int v,int w)
{
edge[++cnt].nex=head[u];
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt;
}
void init()
{
memset(head,-1,sizeof(head));
memset(dep,0,sizeof(dep));
memset(cur,0,sizeof(cur));
memset(inq,0,sizeof(inq));
memset(g,0,sizeof(g));
memset(e,0,sizeof(e));
cnt=-1;
}

bool bfs()
{
queue<int>que;
memset(dep,0,sizeof(dep));
dep[s]=1;
que.push(s);
while(!que.empty())
{
int u=que.front();
que.pop();
for(int i=head[u]; i!=-1; i=edge[i].nex)
{
int v=edge[i].to;
if((dep[v]==0)&&edge[i].w>0)
{
dep[v]=dep[u]+1;
que.push(v);
}
}
}
if(dep[t]>0)
return 1;
return 0;
}

int dfs(int u,int flow)
{
if(u==t)
return flow;
for(int &i=cur[u]; i!=-1; i=edge[i].nex)
{
int v=edge[i].to;
if((dep[v]==dep[u]+1)&&(edge[i].w!=0))
{
int d=dfs(v,min(flow,edge[i].w));
if(d>0)
{
edge[i].w-=d;
edge[i^1].w+=d;
return d;
}
}
}
return 0;
}

int Dinic()
{
int ans=0;
while(bfs())
{
for(int i=1; i<=n; i++)
cur[i]=head[i];
while(int d=dfs(s,inf))
{
ans+=d;
}
}
return ans;
}


void spfa(int s)
{
fill(dis,dis+1+n,1e9);
memset(inq,0,sizeof(inq));
queue<int>que;
que.push(s);
inq[s]=1;
dis[s]=0;
while(!que.empty())
{
int u=que.front();
que.pop();
inq[u]=0;
for(int v=1; v<=n; v++)
{
int w=g[u][v];
if(!w)
continue;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!inq[v])
{
inq[v]=1;
que.push(v);
}
}
}
}
}


int main()
{
//起点是1 终点是n
int time;
scanf("%d",&time);
while(time--)
{
init();
scanf("%d %d",&n,&m);
for(int i=1; i<=m; i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
g[a][b]=1;
g[b][a]=1;
e[a][b]=e[b][a]=c;
}
spfa(1);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(dis[j]-dis[i]==1&&e[i][j]!=0)
add_edge(i,j,e[i][j]),add_edge(j,i,0);
}
}
s=1,t=n;
cout<<Dinic()<<endl;
}
return 0;
}

D:

$对R \le 1, R \le 2, (R-L) \le 2,L=0分开讨论 \\
其它情况都有一种最优策略。$


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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll l,r;
while(~scanf("%lld %lld",&l,&r))
{
if(r<=1)
{
puts("0");
continue;
}
if(r<=2)
{
puts("1");
continue;
}

if(r-l<=2)
{
puts("2");
continue;
}
if(l==0)
{
ll ans=(r-3)/2+2;
printf("%lld\n",ans);
continue;
}
else
{
ll ans=2;
if((r-l-2)&1) ans+=(r-l-3)/2;
else ans+=(r-l-2)/2;
printf("%lld\n",ans);
}
}
}

L:

$二分+优先队列的做法会被卡常,做些预处理可以水过, \\
正解是利用单调性模拟优先队列优化掉一个log。$


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
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
#define ll long long
int n;
ll cost;
ll num[maxn];
ll pre[maxn];
bool check(int x)
{
priority_queue< ll,vector<ll>,greater<ll> >q;
ll ans=0,sum=0;
ll d=(n-1)%(x-1)+1;
if(d>1)
{
ans=pre[d];
q.push(pre[d]);
for(int i=d+1; i<=n; i++)
q.push(num[i]);
}
else
{
for(int i=1; i<=n; i++)
q.push(num[i]);
}
while(!q.empty())
{
sum=0;
for(int i=1; i<=x; i++)
{
sum+=q.top();
q.pop();
}
ans+=sum;
if(ans>cost)
return false;
if(!q.empty())
q.push(sum);
}
if(ans<=cost)
return true;
else
return false;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%lld",&n,&cost);
for(int i=1; i<=n; i++)
{
scanf("%lld",&num[i]);
}
sort(num+1,num+1+n);
pre[1]=num[1];
for(int i=2; i<=n; i++)
pre[i]=pre[i-1]+num[i];
int l=2,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}
printf("%d\n",l);
}
}

L:

$本质不同的排列远小于询问数量,所以先预处理,预处理时用 \\
bitset加速01背包。$


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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int num[60];
int ans[55][55][55];
int tem[5];
int t,n,q;
bitset<90>b[15];
void read(ll& x)
{
int f = 1;
x = 0;
char ch = getchar();

while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}

void read(int& x)
{
int f = 1;
x = 0;
char ch = getchar();

while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
///--------------head--------------------///
inline void solve(int x,int y,int z)
{
for(int i=0; i<=11; i++)
b[i].reset();
b[0][0]=1;
for(int i=1; i<=n; i++)
{
if(num[i]>87||i==x||i==y||i==z)
continue;
for(int j=10; j>=1; j--)
b[j]|=b[j-1]<<num[i];
}
if(b[10][87]==1)
ans[x][y][z]=1;
}

int main()
{
scanf("%d",&t);
while(t--)
{
memset(ans,0,sizeof(ans));
read(n);
for(int i=1; i<=n; i++)
read(num[i]);
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++)
for(int k=j; k<=n; k++)
{
solve(i,j,k);
}
read(q);
while(q--)
{
read(tem[1]),read(tem[2]),read(tem[3]);
sort(tem+1,tem+4);
if(ans[tem[1]][tem[2]][tem[3]])
puts("Yes");
else
puts("No");
}
}
}
avatar Decaku 菜菜菜