佛山2015市选1比赛总结

佛山2015市选1比赛总结
题目

比赛经历

先切了T3、T4,回头发现T1很简单,最后杠T2
%akc,100分钟想完所有题然后码完
巨大心理压力有木有
然后rose和我一起杠T2,没什么想法,只能打个暴力

评测经历

wocT4的MLE是什么鬼,一度心态爆炸,明明算过的
原来是师兄空间只开了64mb
最后[100/100]+[0/98]+[63/99]+[98/98]=261/395
最后混了个初三rk2
%ch文件名打错,实际比我高20,屈居rk3
%lhp做过原题虐场,306全场最高

T1_Analysis

请先思考后再展开

对于后面的点,没有人覆盖它,只能自己解决问题的
从这些点入手,倒推即可

T1_Code_原

请先思考后再展开
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<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=100;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mp[MAXN][MAXN];
char s[MAXN];
int main()
{
freopen("change.in","r",stdin);
freopen("change.out","w",stdout);
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++) mp[i][j]=s[j]-'0';
}
int ans=0;
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
{
if(mp[i][j])
{
ans++;
for(int a=1;a<=i;a++)
for(int b=1;b<=j;b++)
mp[a][b]=1-mp[a][b];
}
}
printf("%d",ans);
}

T2_Analysis

请先思考后再展开

这道题考的时候写了个暴力搜索+hash判重,然后成功炸空间
其实这题的正解违背【数据范围自适应】定律:把矩阵的元素加起来……

其实不是很会证明,但大概可以猜个结论?
比如说因为总是偶数个,所以最优解不会有浪费?
反正没分

然后一个价值30分的细节:
有种情况是,点虽然独立,但没有边和它相连,
这种情况的话是不算非法的……
很难想到啊

T2_Code_原

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=60;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n;
struct Nod
{
int mp[MAXN][MAXN];
int now,p;
};
set<ull> has;
const ull base=131;
bool bk;
ull gethas(Nod x)
{
ull ans=x.now;
bk=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
ans=ans*base+x.mp[i][j];
if(x.mp[i][j]!=0 and x.mp[i][j]<=9) bk=0;
}
return ans;
}
queue<Nod> q;
int bfs()
{
while(!q.empty())
{
Nod now=q.front();q.pop();
int x=now.now;
for(int y=1;y<=n;y++)
if(x!=y and now.mp[x][y]<=9)
{
Nod nx=now;nx.p=now.p+1;nx.now=y;
if(nx.mp[x][y]>0) nx.mp[x][y]--;
ull hs=gethas(nx);
if(bk) return nx.p;
if(has.count(hs)) continue;
has.insert(hs);q.push(nx);
}
}
return -1;
}
char str[MAXN];
int main()
{
freopen("snow.in","r",stdin);
freopen("snow.out","w",stdout);
int T;scanf("%d",&T);
while(T--)
{
Nod st;st.p=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
for(int j=1;j<=n;j++)
{
st.mp[i][j]=str[j]-'0';
if(st.mp[i][j]==0) st.mp[i][j]=10;
}
}
has.clear();
while(!q.empty()) q.pop();
q.push(st);has.insert( gethas(st) );
printf("%d\n",bfs());
}
}

T2_Code_std

请先思考后再展开
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=60;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int fa[MAXN];
int findfa(int x)
{
if(fa[x]!=x) fa[x]=findfa(fa[x]);
return fa[x];
}
void join(int x,int y)
{
int fx=findfa(x),fy=findfa(y);
if(fx!=fy) fa[fx]=fy;
}
int n;
char str[MAXN];
int main()
{
freopen("snow.in","r",stdin);
freopen("snow.out","w",stdout);
int T;scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
bool bk2=0;
for(int j=1;j<=n;j++)
{
int t=str[j]-'0';
if(t>0) ans+=t,join(i,j),bk2=1;
}
if(!bk2) fa[i]=0;//debug 特判独立点
}
bool ok=1;
int rt=findfa(1);
for(int i=2;i<=n;i++)
if(findfa(i)!=rt and fa[i]>0)
ok=0;
if(!ok) puts("-1");
else printf("%d\n",ans);
}
}

T3_Analysis

请先思考后再展开

一眼查分约束
然后就被一个关键句卡了:“栋栋给的分数都是0到10000的正整数”

真的不知道怎么做了这道题
其实题意也很不清晰呀
弃了

T3_Code_原

请先思考后再展开
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<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=11000,MAXM=410000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n;
struct Nod
{
int hou;
int dis;
int ru;
bool v;
Nod()
{
hou=v=0;
ru=0;
//dis=INF;
dis=-INF;
}
}p[MAXN];
struct Edge
{
int y,g,c;
}e[MAXM];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
}
queue<int> q;
int spfa()
{
q.push(1);p[1].dis=0;p[1].v=1;p[1].ru++;
while(!q.empty())
{
int x=q.front();q.pop();
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dis<p[x].dis+e[k].c)
//if(p[y].dis>p[x].dis+e[k].c)
{
p[y].dis=p[x].dis+e[k].c;
if(!p[y].v)
{
p[y].v=1;
q.push(y);
p[y].ru++;
if(p[y].ru>n) return -1;
}
}
}
p[x].v=0;
}
return 1;
}
int main()
{
freopen("grade.in","r",stdin);
freopen("grade.out","w",stdout);
int m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,x;scanf("%d%d%d",&a,&b,&x);
//ins(a,b,-x);
ins(b,a,x);
}
if(spfa()<0) printf("impossible");
else printf("%d",p[n].dis);
}

T4_Analysis

请先思考后再展开

网络流即可
记得要拆点!akc和hanks_o都忘记了

T4_Code_原

请先思考后再展开
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
157
158
159
160
161
162
163
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=40;
const int INF=0x3f3f3f3f;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int getid(int x,int y) {return (x-1)*30+y;}
queue<int> q;
int hou[5000];
struct Edge
{
int y,g,c;
int oth;
}e[8000000];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=hou[x];hou[x]=ln;
ln++;
e[ln].y=x;e[ln].c=0;
e[ln].g=hou[y];hou[y]=ln;
e[ln-1].oth=ln;e[ln].oth=ln-1;
}
int st,ed;
int h[5000];
bool bfs()
{
memset(h,0,sizeof h);h[st]=1;
q.push(st);
while(!q.empty())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(e[k].c>0 and h[y]==0)
{
h[y]=h[x]+1;
q.push(y);
}
}
}
return h[ed]>0;
}
int dfs(int x,int f)
{
if(x==ed) return f;
int out=0;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(e[k].c>0 and h[y]==h[x]+1 and out<f)
{
int tmp=dfs(y,mymin(f-out,e[k].c));
out+=tmp;e[k].c-=tmp;e[e[k].oth].c+=tmp;
}
}
if(out==0) h[x]=0;
return out;
}
int n,m,k;
int mp[MAXN][MAXN];
struct Node
{
int x,y,p;
Node(int a=0,int b=0,int c=0) {x=a,y=b,p=c;}
};
queue<Node> q2;
const int tx[4]={0,0,-1,1};
const int ty[4]={-1,1,0,0};
bool v[MAXN][MAXN];
void make(int stx,int sty)
{
memset(v,0,sizeof v);
q2.push( Node(stx,sty,0) );
while(!q2.empty())
{
Node now=q2.front();q2.pop();
if(now.p>=k) continue;
int x=now.x,y=now.y;
for(int t=0;t<=3;t++)
{
int nx=x+tx[t],ny=y+ty[t];
if(1<=nx and nx<=n and 1<=ny and ny<=m and !v[nx][ny])
{
if(mp[nx][ny]==1) q2.push( Node(nx,ny,now.p+1) );
if(mp[nx][ny]==3) ins(2000+getid(stx,sty),3000+getid(nx,ny),1);
if(mp[nx][ny]==4) ins(getid(nx,ny),1000+getid(stx,sty),1);
v[nx][ny]=1;
}
}
}
}
char str[MAXN];
int main()
{
freopen("jobs.in","r",stdin);
freopen("jobs.out","w",stdout);
int T;scanf("%d",&T);
while(T--)
{
ln=0;memset(hou,0,sizeof hou);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
for(int j=1;j<=m;j++)
{
if(str[j]=='X') mp[i][j]=0;
if(str[j]=='.') mp[i][j]=1;
if(str[j]=='W') mp[i][j]=2;
if(str[j]=='G') mp[i][j]=3;
if(str[j]=='S') mp[i][j]=4;
}
}
st=0;ed=4000;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(mp[i][j]==2)
{
make(i,j);
ins(1000+getid(i,j),2000+getid(i,j),1);
}
if(mp[i][j]==3) ins(3000+getid(i,j),ed,1);
if(mp[i][j]==4) ins(st,getid(i,j),1);
}
int ans=0;
while(bfs()) ans+=dfs(st,INF);
printf("%d\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/4bc4.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%