比赛链接：https://atcoder.jp/contests/agc039/tasks。
A - Connection and Disconnection
找到两个不同的字符切开，每一段就不影响了。
如果没有就特判下。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int n,k;
char s[maxn];
int solve(int l,int r) {
int t=1,res=0;
for(int i=l+1;i<=r;i++)
if(s[i]==s[i-1]) t++;
else res+=t/2,t=1;
res+=t/2;return res;
}
int main() {
scanf("%s",s+1);read(k);n=strlen(s+1);int p=0;
for(int i=2;i<=n;i++) if(s[i]!=s[i-1]) p=i;
if(!p) return printf("%lld\n",1ll*k*n/2),0;
for(int i=n+1;i<=n+p-1;i++) s[i]=s[i-n];
printf("%lld\n",1ll*solve(p,p+n-1)*(k-1)+solve(1,n));
return 0;
}
|
B - Graph Partition
以每个点为起点分层图染色就行了，用到颜色的数量就是答案，注意判不合法情况。
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;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
char s[maxn];
int head[maxn],tot,n,col[maxn],ans,c;
struct edge{int to,nxt;}e[maxn<<1];
void ins(int u,int v) {
e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int bfs(int s) {
queue<int > q;q.push(s);
while(!q.empty()) {
int x=q.front();q.pop();c=max(c,col[x]);
for(int i=head[x];i;i=e[i].nxt)
if(!col[e[i].to]) col[e[i].to]=col[x]+1,q.push(e[i].to);
else if(abs(col[e[i].to]-col[x])!=1) return 0;
}return 1;
}
int main() {
read(n);
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
for(int j=i+1;j<=n;j++) if(s[j]=='1') ins(i,j),ins(j,i);
}
int ans=-1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) col[j]=0;
col[i]=1;c=0;
if(bfs(i)) ans=max(ans,c);
}write(ans);
return 0;
}
|
C - Division by Two with Something
手动模拟下小样例或者推一下可以发现，一个串操作$x$次之后能按位取反当且仅当对于任意$i$满足$s_i=s_{i-x}~{\rm xor}~1$。
并且显然$x$要满足$x|n$，并且$n/x$为奇数，否则操作之前的串最后一截就会等于操作之后前面一截，不符合条件。
那么就可以$O(n)$的算出有多少种小于给定串的串可以在至多$x$次操作后按位取反。
那么容斥一下就可以得到答案了。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
char s[maxn];
int vis[maxn],f[maxn],n,t[maxn],cnt[maxn];
int calc(int x) {
int ans=0;
for(int i=1;i<=x;i++) ans=((ans<<1)|s[i])%mod,t[i]=s[i];
for(int i=x+1;i<=n;i++) t[i]=t[i-x]^1;
for(int i=1;i<=n;i++) {
if(s[i]>t[i]) return ans+1;
if(s[i]<t[i]) return ans;
}return ans+1;
}
int main() {
read(n);scanf("%s",s+1);
for(int i=1;i<=n;i++) s[i]-='0';
for(int i=1;i<=n;i++) if(n%i==0&&((n/i)&1)) vis[n/i]=1,f[n/i]=calc(i);
int ans=0;
for(int i=n;i;i--) {
if(!vis[i]) continue;
for(int j=i<<1;j<=n;j+=i) if(vis[j]) f[i]=(f[i]-f[j]+mod)%mod;
ans=(ans+1ll*n/i*2*f[i]%mod)%mod;
}write(ans);
return 0;
}
|
D - Incenters
我完全不会的几何题。。题解都看了好久才看懂。。
对于$\triangle ABC$，设$A^\prime$为弧$BC$不经过$A$的中点，$B’,C’$同理，那么可以发现$\triangle A’B’C’$的垂心和$\triangle ABC$的内心重合。
根据欧拉线定理（可以上百度搜，讲的还挺对的我也是第一次知道这玩意），设$\triangle ABC$的垂心，重心，外心为$H,G,O$，那么有$H,G,O$共线，并且$2|GO|=|HG|$。
注意到这题中外心就是$(0,0)$，而重心是三点坐标加起来除以二，所以垂心就是三点坐标之和。
接下来的事就很简单了，我们只需要统计每个$A’$点出现的次数，加起来就可以了，因为$A’$点有$O(n^2)$个，所以复杂度为$O(n^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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
const lf pi = acos(-1);
int n,L,t[maxn];
lf x,y;
void get(int a,int b) {
if(a>b) {
lf p=(t[b]+L-t[a])/2.0;
lf w=1.0*t[a]+p;if(w>L) w-=L;
x+=cos(2.0*pi*w/L)*(a-b-1);
y+=sin(2.0*pi*w/L)*(a-b-1);
} else {
lf w=(t[a]+t[b])/2.0;
x+=cos(2.0*pi*w/L)*(n-(b-a+1));
y+=sin(2.0*pi*w/L)*(n-(b-a+1));
}
}
int main() {
read(n),read(L);
for(int i=1;i<=n;i++) read(t[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) get(i,j);
lf pps=1.0*n*(n-1)*(n-2)/6.0;
printf("%.10lf %.10lf\n",x/pps,y/pps);
return 0;
}
|
E - Pairing Points
又是我不会的神仙题。。不过比前一题小清新多了。
首先枚举$1$连的点，假设是$i$。
注意到必然有一个点对会横跨$(1,i)$这条边，否则不连通，那么我们枚举最上面那个，假设是$(j,k)$ $(j<k)$。
因为我们枚举的是最上面那条边，所以$[2,j-1]$不会和$[i,n]$连边，同理$[j+1,n-1]$不会和$[2,i]$连边。
所以$[2,j-1]$只会在自己内连边或连向$[j+1,i-1]$，并且$[j+1,i-1]$一定会有一个分界点，假设是$s$，那么$[2,j-1]$只会向$[j+1,s]$连边，而$[s+1,i-1]$也只会向另一边连边。
假设另一边的分界点为$t$，那么问题被分成了三个子问题：$[2,j-1]\sim [j+1,s]$，$[s+1,i-1]\sim [i+1,t-1]$，$[t,k-1]\sim [k+1,n]$。
所以写个记忆化搜索就行了，复杂度应该是常数非常小的$O(n^7)$，足以通过本题。
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
| #include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 40+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
char c[maxn][maxn];
int n;
ll f[maxn][maxn][maxn];
ll dfs(int l,int r,int mid) {
if(f[l][r][mid]!=-1) return f[l][r][mid];
if(l==r) return 1;
if(l==mid||r==mid) return 0;
ll ans=0;
for(int j=l;j<mid;j++)
for(int k=mid+1;k<=r;k++) {
if(c[j][k]=='0') continue;
for(int s=j;s<mid;s++)
for(int t=mid+1;t<=k;t++)
ans+=dfs(l,s,j)*dfs(t,r,k)*dfs(s+1,t-1,mid);
}
return f[l][r][mid]=ans;
}
int main() {
read(n);n<<=1;for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
ll ans=0;memset(f,-1,sizeof f);
for(int i=2;i<=n;i++) if(c[1][i]=='1') ans+=dfs(2,n,i);
printf("%lld\n",ans);
return 0;
}
|