栗子栗子

CodeForces 745 解题报告

思路

A

在原串后面接一个,暴力搞就好了

B

观察发现,不能旋转的情况下,原来不是矩形,就怎么都拼不成矩形了

关于原来是不是矩形,维护左上右下顶点坐标就完了

C

统计一下每个点属于哪个连通分量(含政府),将多余的点放入点数最多的连通分量里

然后算下最多能连多少边减去总数就可以了

D

考虑1000以内的数的二进制表示最多十位

我们每次查询固定某一二进制位为0和为1的所有数

然后统计,对于第i行,我们要避开第i个,那么若i的第j位为0,我们就查询j位为1的所有数,反之亦然

就可以避开i,但是查询到其余所有数了

E

玄学题目,首先考虑对于一张卡,若其所需要的某一$tokens(≥n)$,那么一定会需要额外的回合赚tokens

我们预先搞定这些额外的回合,将其需要的tokens变成n

然后考虑贪心地去买card,每次购买完毕后必有某一种$tokens$数目为0

因此我们DP解决,同时需要状态压缩

$dp_{mask,flag,other}$表示当前状态为mask时,flag表示的$tokens$为0,另一种有other个的状态,转移即可

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
map<string,int> m;
char s[105];
int n,i,ans;
string ss;

int main()
{
gets(s+1);
n=strlen(s+1);
for(i=n+1;i<=2*n-1;i++)s[i]=s[i-n];
for(i=1;i<=n;i++)
{
ss="";
for(int j=i;j<=i+n-1;j++)ss+=s[j];
if(m[ss]>0)continue;
m[ss]=1;ans++;
}
printf("%d",ans);
return 0;
}

B

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
char s[505][505];
int l,r,u,d;
int i,j,n,m;

bool judge()
{
for(i=u;i<=d;i++)
for(j=l;j<=r;j++)
if(s[i][j]=='.')return false;
return true;
}

int main()
{
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)gets(s[i]+1);
l=m+1,u=n+1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(s[i][j]=='.')continue;
l=min(l,j);r=max(r,j);
u=min(u,i);d=max(d,i);
}
if(judge())printf("YES");else printf("NO");
return 0;
}

C

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
int a[1005];
vector<int> g[1005];
int gov[1005];
int f[1005],tot[1005],cal[1005];
int i,j,k,l,m,n;
int num,ans;

int find(int t)
{
if(f[t]==t)return t;
else return f[t]=find(f[t]);
}

int main()
{
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)f[i]=i,tot[i]=1;
for(i=1;i<=k;i++)scanf("%d",&gov[i]);
for(i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int xx=find(x),yy=find(y);
if(xx==yy)continue;
tot[xx]+=tot[yy];f[yy]=f[xx];
}
num=0;
for(i=1;i<=k;i++)
{
cal[i]=tot[find(gov[i])];
num+=cal[i];
}
sort(cal+1,cal+k+1);
cal[k]+=n-num;
for(i=1;i<=k;i++)
{
ans+=cal[i]*(cal[i]-1)/2;
}
printf("%d",ans-m);
return 0;
}

D

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
vector<int> g[15][2];
int ans[1005][15][2];
int used[15];
int da[1005];
int i,j,k,l,m,n;

void QA(int x,int y)
{
printf("%d\n",g[x][y].size());
for(unsigned int t=0;t<g[x][y].size();t++)
{
if(t>0)printf(" ");
printf("%d",g[x][y][t]);
}
printf("\n");
fflush(stdout);
for(int t=1;t<=n;t++)scanf("%d",&ans[t][x][y]);
}

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
j=i;k=0;
while(j>0)
{
k++;g[k][j&1].push_back(i);
if(j&1)used[k]=1;
j>>=1;
}
while(k<10)g[++k][0].push_back(i);
}
for(i=1;i<=n;i++)
for(j=1;j<=10;j++)ans[i][j][0]=ans[i][j][1]=1e9+7;
for(i=1;i<=10;i++)
{
if(used[i]<=0)break;
if(g[i][0].size()>0)QA(i,0);
if(g[i][1].size()>0)QA(i,1);
}
for(i=1;i<=n;i++)
{
da[i]=1e9+7;k=i;
for(j=1;j<=10;j++)
{
da[i]=min(da[i],ans[i][j][(k&1)^1]);
k>>=1;
}
}
printf("-1\n");
for(i=1;i<=n;i++)
{
if(i>1)printf(" ");
printf("%d",da[i]);
}
fflush(stdout);
return 0;
}

E(mine)

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
int a[70005][3][300];
struct info
{
int red,blue;
int xx;
}b[20],d[20];
vector<int> g[20];
int i,j,k,l,m,n,r,tot,ans;
int sum[3];
char c;
int xl,xr;

int main()
{
IN;l=0;
scanf("%d\n",&n);m=n*n;
for(i=1;i<=n;i++)
{
scanf("%c %d %d\n",&c,&b[i].red,&b[i].blue);
if(c=='R')b[i].xx=1;else b[i].xx=2;
if(b[i].red>=n || b[i].blue>=n)
{
xl+=max(0,b[i].red-n);
xr+=max(0,b[i].blue-n);
b[i].red=min(n,b[i].red);
b[i].blue=min(n,b[i].blue);
}
}
for(i=0;i<(1<<n);i++)
{
j=i;k=0;
while(j>0)
{
if(j&1)k++;
j>>=1;
}
g[k].push_back(i);
}
for(i=0;i<(1<<n);i++)
for(j=0;j<=n*n;j++)
a[i][1][j]=a[i][2][j]=1e9;
//if(xl>xr)a[0][2][xl-xr]=0;else a[0][1][xr-xl]=0;
if(xl>xr)a[0][1][min(xl-xr,n*n)]=0;else a[0][2][min(xr-xl,n*n)]=0;
if(xl==xr)a[0][1][0]=a[0][2][0]=0;
for(int w=1;w<=n;w++)
{
for(i=0;i<g[w].size();i++)
{
int now=g[w][i];
sum[1]=sum[2]=0;
for(j=0;j<n;j++)if((now & (1<<j)))sum[b[j+1].xx]++;
for(j=0;j<n;j++)
{
if((now & (1<<j))==0)continue;
l=sum[1];r=sum[2];
if(b[j+1].xx==1)l--;else r--;
int la=now^(1<<j);
//printf("%d %d\n",now,la);
for(k=0;k<=n*n;k++)
{
if(a[la][1][k]<1e9)
{
int nl=0,nr=k;
int nred=max(0,b[j+1].red-l-nl);
int nblue=max(0,b[j+1].blue-r-nr);
tot=max(nred,nblue);
int re=tot+nl-max(0,b[j+1].red-l);
int bl=tot+nr-max(0,b[j+1].blue-r);
if(re==0)a[now][1][min(bl,n*n)]=min(a[now][1][min(bl,n*n)],a[la][1][k]+tot);
if(bl==0)a[now][2][min(re,n*n)]=min(a[now][2][min(re,n*n)],a[la][1][k]+tot);
}
if(a[la][2][k]<1e9)
{
int nl=k,nr=0;
int nred=max(0,b[j+1].red-l-nl);
int nblue=max(0,b[j+1].blue-r-nr);
tot=max(nred,nblue);
int re=tot+nl-max(0,b[j+1].red-l);
int bl=tot+nr-max(0,b[j+1].blue-r);
if(re==0)a[now][1][min(bl,n*n)]=min(a[now][1][min(bl,n*n)],a[la][2][k]+tot);
if(bl==0)a[now][2][min(re,n*n)]=min(a[now][2][min(re,n*n)],a[la][2][k]+tot);
}
}
}
}
}
l=r=0;k=(1<<n)-1;
ans=1e9;
for(i=0;i<=n*n;i++)
{
ans=min(ans,a[k][1][i]);
ans=min(ans,a[k][2][i]);
}
//for(i=0;i<=n*n;i++)printf("%d %d %d\n",i,a[k][1][i],a[k][2][i]);
printf("%d",ans+n+max(xl,xr));
return 0;
}

E(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
struct card
{
int xx,red,blu;
//card(int xx=0,int x=0,int y=0):xx(xx),x(x),y(y){}
}a[20];

int dp[70005][2][300];
int i,n;
int xl,xr,ans;

int solve(int now,int re,int ot)//0为红0,1为蓝0
{
int ret=1<<29;
ot=min(ot,n*n);
if(now==(1<<n)-1)return 0;
if(dp[now][re][ot]>=0)return dp[now][re][ot];
int hr=0,hb=0;
for(int j=0;j<n;j++)
if((now>>j)&1)
{
if(a[j+1].xx==1)hr++;else hb++;
}
int tr=0,tb=0;
if(re==0)tb=ot;else tr=ot;
for(int j=0;j<n;j++)
{
if((now>>j)&1)continue;
int ne=now|(1<<j);
card t=a[j+1];
int mo=max(t.red-(hr+tr),t.blu-(hb+tb));
mo=max(0,mo);
int nr=mo+tr-max(0,t.red-hr);
int nb=mo+tb-max(0,t.blu-hb);
if(nr==0)ret=min(ret,mo+solve(ne,0,nb));
if(nb==0)ret=min(ret,mo+solve(ne,1,nr));
}
return dp[now][re][ot]=ret;
}

int main()
{
IN;
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
char c;
scanf("%c %d %d\n",&c,&a[i].red,&a[i].blu);
if(c=='R')a[i].xx=1;else a[i].xx=2;
xl+=max(0,a[i].red-n);a[i].red=min(a[i].red,n);
xr+=max(0,a[i].blu-n);a[i].blu=min(a[i].blu,n);
}
for(i=0;i<(1<<n);i++)
for(int j=0;j<=n*n;j++)
dp[i][0][j]=dp[i][1][j]=-1;
ans=max(xl,xr)+n;
if(xl<=xr)
ans+=solve(0,1,xr-xl);
else
ans+=solve(0,0,xl-xr);
printf("%d",ans);
return 0;
}