| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 9/13 | O | O | Ø | . | O | O | O | O | . | O | . | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：2015 ACM-ICPC Asia Changchun Regional Contest
A Too Rich
题目描述
给定一些价值为$1,5,10,20,50,100,200,500,1000,2000$的金币，要用最多的个数表示给定的$p$，问最多个数是多少。
解题思路
反向思考，求一下表示$sum-p$最小的个数。可以贪心的从上到下求解，对于每一种金币，每次选的个数必然是$max$或$max-1$（$max$代表到当前状态选这种金币最多能选的个数），否则显然不优（更低价值的金币必然能够被更高价值金币表示）。
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 10 * 2;
const int inf = 0x3f3f3f3f;
int f[ms], a[ms];
int n, res;
void dfs(int x, int val, int m)
{
if (x == -1)
{
if (val == 0)
{
res = min(m, res);
}
return;
}
int tmp = min(f[x], val / a[x]);
dfs(x - 1, val - tmp * a[x], m + tmp);
if (tmp > 0)
{
tmp--;
dfs(x - 1, val - tmp * a[x], m + tmp);
}
}
int main()
{
a[0] = 1;
a[1] = 5;
a[2] = 10;
a[3] = 20;
a[4] = 50;
a[5] = 100;
a[6] = 200;
a[7] = 500;
a[8] = 1000;
a[9] = 2000;
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int sum = 0;
int cnt = 0; res = inf;
for (int i = 0; i < 10; ++i)
{
scanf("%d", &f[i]);
sum += a[i] * f[i];
cnt += f[i];
}
if (sum < n)
{
res = -1;
}
else if (sum == n)
{
res = cnt;
}
else
{
dfs(9, sum - n, 0);
if (res != inf)
res = cnt - res;
else
res = -1;
}
printf("%d\n", res);
}
return 0;
}
B Count a × b
题目描述
定义$f(m)$为满足$0\leq i\leq m-1,0\leq j\leq m-1,i\times j\space mod \space m\neq 0$的二元组$(i,j)$个数。
求$g(n)=\sum_{m|n}f(m)$。
解题思路
求$ij\space mod\space m\neq 0$的个数可转化为求$m|ij$的个数，即求原表格中$0$的个数：
$f(m)=m^2-\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}[m|ij]$
显然，求和符号从$0$到$m-1$和从$1$到$m$是等价的。于是考虑$[1,m]\times [1,m]$的表格，对于第$i$行，满足$m|ij$的$j$可以从$\frac mg,2\frac mg,…,g\frac mg$中取得，其中$g=gcd(m,i)$。也即，对于每个$gcd(m,i)=g$的$i$，对二元组$(i,j)$的贡献均为$g$。
枚举$m$的因子$g$，对于每个$g$，满足条件（$gcd(m,i)=g,1\leq i\leq m$）的$i$的个数为$\phi(\frac mg)$，其中$\phi(x)$为欧拉函数，表示$<x$且与$x$互质的数的个数（证明：$gcd(m,i)=g,gcd(\frac mg,\frac ig)=1$，对于每一个与$\frac mg$互质且小于$\frac mg$的数$x$，有$i=xg\leq m$）。于是式子转化为：
$f(m)=m^2-\sum_{g|m}g\times \phi(\frac mg)=m^2-\sum_{xy=m}x\phi(y)$
于是$g(n)=\sum_{m|n}(m^2-\sum_{xy=m}x\phi(y))=\sum_{m|n}m^2-\sum_{xy|n}x\phi(y)$
对于前半部分，每个$1e9$以内的数的因数个数$\leq 1344$，因此可以直接暴力枚举因数求解；也可质因数分解后变为$\prod (1+p_i^2+p_i^4+…+p_i^{2k_i})$的形式再预处理解决。
对于后半部分，枚举$x,y$，变为$\sum_{x|n}x\sum_{y|\frac nx}\phi(y)$。而欧拉函数和$e=[n=1]$的狄利克雷卷积为$id$，故$\sum_{d|n}\phi(d)=n$，即原式$=\sum_{x|n}x\frac nx=\sum_{x|n} n$。暴力枚举因数即可。
AC代码
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
typedef long long ll;
using namespace std;
int np[N],cnt;
ll phi[N],p[N];
void sieve(){
int i,j;np[0]=np[1]=1;
for(i=2;i<N;i++){
if(!np[i])p[cnt++]=i,phi[i]=i-1;
for(j=0;j<cnt;j++){
if(p[j]*i>=N)break;
np[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}else phi[i*p[j]]=phi[i]*phi[j];
}
}
}
unsigned long long pw[N][35];
void init(){
int i,j;
for(i=0;i<cnt;i++)pw[i][0]=1;
for(i=0;i<cnt;i++)
for(j=1;j<35;j++)
pw[i][j]=pw[i][j-1]*p[i]*p[i];
for(i=0;i<cnt;i++)
for(j=1;j<35;j++)
pw[i][j]+=pw[i][j-1];
}
int main(){
int t,i,n;
scanf("%d",&t);
sieve();
init();
while(t--){
scanf("%d",&n);
unsigned long long tmp=n;
vector<pair<int,int>>fac;
for(i=0;i<cnt;i++){
if(tmp%p[i]==0){
int num=0;
while(tmp%p[i]==0)num++,tmp/=p[i];
fac.push_back(make_pair(i,num));
}
}
unsigned long long now=1;
if(tmp>1)now=tmp*tmp+1;
for(auto i:fac)now*=pw[i.first][i.second];
unsigned long long now2=n;
if(tmp>1)now2=now2*2;
for(auto i:fac)now2=now2*(i.second+1);
now2=(1ull<<64)-now2;
printf("%llu\n",now+now2);
}
return 0;
}
C Play a game
题目描述
给一个字符串$s$和一个字符串集合$T$，在$s$上给定的多组区间上玩游戏，每个人可以取走一个开头的元素或结尾的元素，到达空串或$T$中任意一个串的时候，游戏立即结束，下一手要操作的玩家失败，另一方获胜。问都采取最优策略的情况下谁能胜利。
解题思路
$f[i][j]$ 表示当前$[i,j]$区间先手必败还是必胜，先手必败当且仅当$[i,j]$是终止状态或$[i,j-1][i+1,j]$均为必胜状态，先手必胜当且仅当$[i+1,j][i,j-1]$至少有一个是先手必败状态。故$f[i][j]=!(f[i][j-1]\&f[i+1][j])$。
问题转化成了区间$dp$，用$AC$自动机跑出终止状态对应的位置，再进行区间$dp$即可。
但是这样的复杂度太高，会获得$TLE$。
考虑使用$bitset$对区间$dp$进行优化。改变$f[i][j]$的含义，变为当前区间长度为$i$，起始位置为$j$的必胜必败状态。于是有
f[i][j]=~(f[i-1][j]&f[i-1][j+1])， 即f[i]=~(f[i-1]&(f[i-1]>>1))。复杂度$O(\frac{n^2}{64})$，可以勉强卡过。AC代码
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
typedef long long ll;
using namespace std;
//int f[N][N];
bitset<N>f[N];
char a[N],s[N];
vector<int>pos[N];
struct ACAM{
int tr[N][26],tot;
int fail[N],pre[N],num[N],now;
queue<int>Q;
void init(){
tot=0;
num[0]=fail[0]=pre[0]=0;
memset(tr[0],0,sizeof(tr[0]));
}
void insert(char s[]){
int i;
now=0;
for(i=0;s[i];i++){
int p=s[i]-'a';
if(!tr[now][p]){
tr[now][p]=++tot;
num[tot]=fail[tot]=pre[tot]=0;
memset(tr[tot],0,sizeof(tr[tot]));
}
now=tr[now][p];
}
num[now]=i;
}
void build(){
int i;
for(i=0;i<26;i++)if(tr[0][i])Q.push(tr[0][i]);
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=0;i<26;i++){
if(tr[p][i]){
fail[tr[p][i]]=tr[fail[p]][i];
Q.push(tr[p][i]);
pre[tr[p][i]]=num[fail[tr[p][i]]]?fail[tr[p][i]]:pre[fail[tr[p][i]]];
}
else tr[p][i]=tr[fail[p]][i];
}
}
}
void solve(char a[]){
int i,now=0;
for(i=0;a[i];i++){
now=tr[now][a[i]-'a'];
int temp=now;
while(temp){
if(num[temp])pos[num[temp]].push_back(i-num[temp]+2);
temp=pre[temp];
}
}
}
}T;
int main(){
int i,t,n,m,q;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// double time=clock();
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&q);
scanf("%s",a);
T.init();
for(i=0;i<=n;i++)pos[i].clear();
for(i=0;i<m;i++){
scanf("%s",s);
T.insert(s);
}
T.build();
T.solve(a);
f[0].reset();
for(i=1;i<=n;i++){
f[i]=~(f[i-1]&(f[i-1]>>1));
for(auto j:pos[i])f[i][j]=0;
}
while(q--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",(int)f[r-l+1][l]);
}
}
// printf("%.5f\n",clock()-time);
return 0;
}
D Pipes selection
题目描述
解题思路
AC代码
2
E Rebuild
题目描述
给定$n$个点组成的多边形，要求以每个点为圆心画圆，相邻两个点之间的圆相切，求最大圆面积之和。
解题思路
任意找一个点作为起始点，设这个点对应半径$r_1$，那么有$r_2=d_{12}-r_1,r_3=d_{23}-r_2,…,r_1=d_{n1}-r_n$
这是一个$n$元$1$次方程组，我们将它化为矩阵，以$4$为例：
$\left(\begin{aligned}1\space1\space0\space 0\\ 0\space 1\space 1\space 0 \\ 0\space0\space1\space1\\ 1\space0\space0\space1\end{aligned}\right)\left(\begin{aligned}r_1\\ r_2\\ r_3\\ r_4\end{aligned}\right)=\left(\begin{aligned}d_{12}\\ d_{23}\\ d_{34}\\ d_{41}\end{aligned}\right)$
化简这个矩阵，当$n$为偶数时矩阵的秩为$n-1$，方程无解或有无穷多组解，解出$r_1$范围后问题转化成一个一元二次方程；$n$为奇数时秩为$n$，方程有唯一解。
AC代码 - by qxforever
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
using namespace std;
typedef long long ll;
const int maxn = 1e5+23;
int T,n;
int a[maxn],b[maxn];
double dis[maxn];
double ans[maxn];
const double eps = 1e-8;
const double pi = acos(-1.0);
bool eq(double a,double b)
{
if(abs(a-b)<eps) return true;
return false;
}
double getd(int i,int j)
{
double aa=a[i],bb=b[i];
double cc=a[j],dd=b[j];
return sqrt((aa-cc)*(aa-cc)+(bb-dd)*(bb-dd));
}
bool check()
{
ans[0]=1;
for(int i=1;i<=n;i++){
ans[i]=dis[i-1]-ans[i-1];
}
return eq(ans[0],ans[n]);
}
int main()
{
cin >> T ;
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d",a+i,b+i);
a[n]=a[0],b[n]=b[0];
double sumd=0;
for(int i=0;i<n;i++){
dis[i]=getd(i,i+1);
sumd+=dis[i];
}
if(n%2==0){
//for(int i=0;i<n;i++) printf("%.2f ",dis[i]);
if(!check()) {printf("IMPOSSIBLE\n");continue;}
double d=0,kl,kr,pred=0;
kl=0,kr=dis[0];
for(int i=1;i<=n;i++){
pred=dis[i-1]-pred;
if(i%2){
kr=min(kr,pred);
}
else{
kl=max(kl,-pred);
}
}
//printf("kk: %.2f %.2f\n",kl,kr);
if(kl>kr+eps) {printf("IMPOSSIBLE\n");continue;}
for(int i=0;i<n-1;i++){
int t=1;
if(i%2==0) t=-1;
d+=1.0*t*(n-i-1)*dis[i];
}
d*=2;
ans[0]=d/(-2*n);
if(ans[0]<kl) ans[0]=kl;
else if(ans[0]>kr) ans[0]=kr;
sumd=ans[0]*ans[0];
for(int i=1;i<n;i++){
ans[i]=dis[i-1]-ans[i-1];
sumd+=ans[i]*ans[i];
}
printf("%.2f\n",pi*sumd);
for(int i=0;i<n;i++) printf("%.2f\n",ans[i]);
}
else{
sumd/=2;
bool can=true;
int t=n/2;
for(int i=0;i<n;i++){
ans[i]=sumd;
for(int j=0;j<t;j++){
int now=(i+1+2*j)%n;
ans[i]-=dis[now];
}
if(ans[i]<0) can=false;
}
if(can){
double sum=0;
for(int i=0;i<n;i++) sum+=ans[i]*ans[i];
printf("%.2f\n",sum*pi);
for(int i=0;i<n;i++) printf("%.2f\n",ans[i]);
}
else{
printf("IMPOSSIBLE\n");
}
}
}
}
F Almost Sorted Array
题目描述
问一个数列能否删掉某个数使得最终序列有序。
解题思路
升序降序讨论一番贪心删除就可以了。
AC代码 - by qxforever
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
using namespace std;
typedef long long ll;
const int maxn = 1e5+23;
int T,n;
int a[maxn];
int main()
{
cin >> T;
while(T--){
scanf("%d",&n);
bool can=true;
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
int mx=-1,cnt=0;
for(int i=1;i<=n;i++){
if(a[i]>=mx){
mx=a[i];
continue;
}
else{
if(cnt==0){
if(a[i]>=a[i-2]){
mx=a[i];
cnt++;
}
else{
cnt++;
}
}
else{
can=false;break;
}
}
}
reverse(a+1,a+n+1);
bool can2=true;
mx=-1,cnt=0;
for(int i=1;i<=n;i++){
if(a[i]>=mx){
mx=a[i];
continue;
}
else{
if(cnt==0){
if(a[i]>=a[i-2]){
mx=a[i];
cnt++;
}
else{
cnt++;
}
}
else{
can2=false;break;
}
}
}
if(can2||can){
printf("YES\n");
}
else printf("NO\n");
}
}
G Dancing Stars on Me
题目描述
整数格上给$n$个点，问是不是正多边形。
解题思路
直接判断正方形即可。
AC代码
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
typedef long long ll;
using namespace std;
double basx,basy;
struct Point{
int x,y;
}a[110];
Point operator-(Point a,Point b){
return (Point){a.x-b.x,a.y-b.y};
}
int dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
int dis2(Point a,Point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int check(int i,int j,int k,int l){
if(fabs(dot(a[j]-a[i],a[l]-a[i]))>1e-8)return 0;
if(fabs(dot(a[i]-a[j],a[k]-a[j]))>1e-8)return 0;
if(fabs(dot(a[l]-a[k],a[j]-a[k]))>1e-8)return 0;
if(fabs(dot(a[k]-a[l],a[i]-a[l]))>1e-8)return 0;
int ds=dis2(a[i],a[j]);
if(ds==dis2(a[j],a[k])&&ds==dis2(a[k],a[l])&&ds==dis2(a[l],a[i]))return 1;
else return 0;
}
int main(){
int i,j,k,l,t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);
if(n!=4){
printf("NO\n");
continue;
}
int flag=0;
for(i=0;i<4;i++){
for(j=0;j<4;j++){
for(k=0;k<4;k++){
for(l=0;l<4;l++){
if(i!=j&&j!=k&&k!=l&&i!=k&&i!=l&&j!=l){
if(check(i,j,k,l))flag=1;
}
}
}
}
}
if(flag)printf("YES\n");
else printf("NO\n");
}
return 0;
}
H Partial Tree
题目描述
给一个函数$f$，让你建一棵树，它的度序列为$d_i$，最大化$\sum_{i=1}^{n}f(d_i)$。
解题思路
先对每一个点连一个度，还剩下$n-2$个度没有被使用，$f[i][j]$记录现在到了第$i$个$f$，用掉了$j$个度的$f$ 的总和最大值。这是一个完全背包问题。
AC代码
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
using namespace std;
typedef long long ll;
const int ms = 2020 * 2;
const int inf = 0x3f3f3f3f;
int f[ms], dp[ms];
int n, m, res, mx;
void solve()
{
mx = n - 2;
for (int i = 0; i <= mx; i++) dp[i] = -inf;
dp[0] = 0;
for (int i = 1; i < n; i++)
{
for (int j = i; j <= mx; j++)
{
if (dp[j - i] != -inf)
dp[j] = max(dp[j], dp[j - i] + f[i]);
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i)
{
scanf("%d", &f[i]);
}
for (int i = 1; i < n - 1; ++i)
{
f[i] -= f[0];
}
if (n > 2)
{
solve();
printf("%d\n", dp[mx] + n * f[0]);
}
else
{
printf("%d\n", n * f[0]);
}
}
return 0;
}
I Chess Puzzle
题目描述
解题思路
AC代码
2
J Chip Factory
题目描述
给定一个数列，求$max(a_i+a_j)\oplus(a_k)$。
解题思路
暴力即可。复杂度$O(\frac 12n^3)$。
也可以将所有元素加入一棵$trie$，再枚举$i,j$进行判断，复杂度$O(n^2\log max)$，常数挺大。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long ll;
using namespace std;
int a[1010];
int main(){
int i,j,k,T,n;
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
for(k=j+1;k<n;k++){
ans=max(ans,(a[i]+a[j])^a[k]);
ans=max(ans,(a[k]+a[j])^a[i]);
ans=max(ans,(a[i]+a[k])^a[j]);
}
}
}
printf("%d\n",ans);
}
return 0;
}
K Maximum Spanning Forest
题目描述
解题思路
AC代码
2
L House Building
题目描述
有一堆立方体积木，给定一个积木高度，求露在外面的表面积。
解题思路
暴力枚举每一层即可。
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 55;
int c[ms][ms];
int n, m, res, mx;
void solve(int x)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (c[i][j] >= x)
{
if (c[i + 1][j] >= x) res--;
if (c[i - 1][j] >= x) res--;
if (c[i][j + 1] >= x) res--;
if (c[i][j - 1] >= x) res--;
}
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m); res = 0, mx = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
scanf("%d", &c[i][j]);
if (c[i][j])
{
res++;
res += 4 * c[i][j];
mx = max(c[i][j], mx);
}
c[i][m + 1] = 0;
c[n + 1][j] = 0;
}
}
for (int i = 1; i <= mx; ++i)
{
solve(i);
}
printf("%d\n", res);
}
return 0;
}
M Security Corporation
题目描述
解题思路
AC代码
2