比赛传送门
作者： fn

---

签到题

G题 Icon Design / 图标设计

题目大意
输出图标"NFLS"。

考察内容
模拟

分析
按题意模拟即可。

#include
using namespace std;
int n;
int main(){
    cin>>n;
    int m = 13*n+19;
    for(int i = 1;i<=m;i++){
        cout<<"*";
    }
    cout<<endl;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(j==1||j==m) cout<<"*";
            else cout<<".";
        }
        cout<<endl;
    }
    //中间字母
    int k = n+3;
    for(int i = 1;i<=2*n+3;i++){
        for(int j = 1;j<=m;j++){
            if(j==1) {cout<<"*";continue;}
            else if(j==n+3) cout<<"@";
            else if(i>=2&&j==k&&j<=3*n+4) {
              cout<<"@"; 
            }
            else if(j==3*n+5) cout<<"@";
            else if((i==1||i==n+2)&&j>=4*n+7&&j<=6*n+9) cout<<"@";
            else if((i!=1&&i!=n+2)&&j==4*n+7) cout<<"@";
            else if(i!=n+2&&i!=2*n+3&&j>4*n+7&&j<6*n+9) cout<<".";
            else if(i!=2*n+3&&j==7*n+11) cout<<"@";
            else if(i==2*n+3&&j>=7*n+11&&j<=9*n+13) cout<<"@";
            else if((i==n+2||i==2*n+3||i==1)&&j>=10*n+15&&j<=12*n+17)cout<<"@";
            else if(i>1&&i<n+2&&j==10*n+15)cout<<"@";
            else if(i<2*n+3&&i>n+2&&j==12*n+17)  cout<<"@";
            else if(j==m) cout<<"*";
            else cout<<".";
        }
        k++;
        cout<<endl;
    }
    
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(j==1||j==m) cout<<"*";
            else cout<<".";
        }
        cout<<endl;
    }
    for(int i = 1;i<=m;i++){
	    cout<<"*";
	}
	cout<<endl;
}
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

---

J题 Number Game / 数字游戏

题目大意
给定 $b1,b2,c$ 和目标值 $x$ ，可以进行任意次赋值，使 $c=b1-c$ 或者 $c=b2-c$ 。
求是否可以使 $c$ 变为 $x$ 。

考察内容
暴力，找规律

分析
$b1!=b2$ 时，多次交替操作后，$c$ 的变化类似等差数列，公差为 $abs(b-b2)$ 。对 $x$ 取模后和各种可能的结果进行判断即可。

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
ll a,b,c,x;
int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>a>>b>>c>>x;
		ll b2=a-b; // 得到另一个b
		
		if(c==x){
			cout<<"Yes"<<endl;
			continue;
		}
		if(b-c==x || b2-c==x){
			cout<<"Yes"<<endl;
			continue;
		}
		
		if(b!=b2){ // b!=b2时，额外进行一些判断 
			if(x==b2-(b-c) || x==b-(b2-c)){
				cout<<"Yes"<<endl;	
				continue;
			}
		
			ll mod=abs(b-b2);
			ll d=x%mod; // 	
			if(d==c%mod || d==c%mod-mod || d==c%mod+mod){
				cout<<"Yes"<<endl;	
				continue;
			}
			if(d==(b-c)%mod || d==(b-c)%mod-mod || d==(b-c)%mod+mod){
				cout<<"Yes"<<endl;	
				continue;
			}
			if(d==(b2-c)%mod || d==(b2-c)%mod-mod || d==(b2-c)%mod+mod){
				cout<<"Yes"<<endl;	
				continue;
			}
			ll t2=(b2-(b-c))%mod;
			if(d==t2%mod || d==t2%mod-mod || d==t2%mod+mod){
				cout<<"Yes"<<endl;	
				continue;
			}
			t2=(b-(b2-c))%mod;
			if(d==t2%mod || d==t2%mod-mod || d==t2%mod+mod){
				cout<<"Yes"<<endl;	
				continue;
			}
		}
		cout<<"No"<<endl;
	}
	return 0;
}
/*
1
4 2 2 20

1
2 4 3 -9

1
2 4 3 15

*/ 
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

---

基本题

B题 Eezie and Pie / 伊兹和馅饼

题目大意

给定一棵有根树，根是结点 $1$ ，城市中有 $n(1\le n\le 2\times 10^6)$ 个结点，每个结点上有一个饼屋。每个饼屋将饼往根结点传递（传递的点包括自己），最大传递距离为 $d_i$。

计算每个结点收到多少个饼。

考察内容
树上差分

分析
类似lca预处理一下，树上倍增求出 $d_i+1$ 辈祖先，然后树上差分。
最后跑一个dfs汇总一下。

#include 
using namespace std;
#define maxn 2000005
#define ll long long
#define int long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
struct Node{
	int to,nxt;
};
Node edge[maxn<<2]; // 链式前向星要多开几倍数组
int head[maxn<<2],power[maxn],n,m,d[maxn],fa[maxn][30],num;
ll dis[maxn];
ll h[maxn]; // 该节点到根节点的距离

inline int read(){ // 快读
	int s=0;
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') s=s*10+c-'0',c=getchar();
	return s;
}
// 链式前向星
inline void add(int x,int y){
	edge[++num].to=y,edge[num].nxt=head[x],head[x]=num;
}
// 初始化
inline void work(int u,int fath){
	d[u]=d[fath]+1; 
	fa[u][0]=fath;
	for (int i=0;fa[u][i];++i) fa[u][i+1]=fa[fa[u][i]][i];
	
	for (int i=head[u];i;i=edge[i].nxt){
		int e=edge[i].to;
		if (e!=fath) work(e,u);
	}
}

// 累计
inline void Get(int u,int fath){
	for (int i=head[u];i;i=edge[i].nxt){
		int e=edge[i].to;
		if (e==fath) continue;
		Get(e,u);
		power[u]+=power[e];
	}
}

ll getfa(int x,int disx){ // 树上倍增求 x 的 disx 辈祖先  
	if(disx>d[x]-1)return 0; // 返回根节点的祖先
	else if(disx==d[x]-1)return 1; // 返回根节点 
	
	// disx
	for (int i=22;i>=0;--i){ // 二进制拆分 
		if (disx >= (1<<i)){
			disx -= (1<<i);
			
			x=fa[x][i]; 
		} 
	} 
	return x;
} 

signed main(){ // 树上差分,AC
	n=read();
	int x,y;
	for (int i=1;i<n;++i){
		x=read(); y=read();
		add(x,y); add(y,x);
	}
	work(1,0); // 类似lca进行预处理 
	for(int i=1;i<=n;i++){
		cin>>dis[i];
	}	
	
	for(int i=1;i<=n;i++){
		x=i;
		y=getfa(x,dis[x]+1); // 树上倍增求dis[x]+1辈祖先

		++power[x]; --power[y]; // 树上差分
	}
	
	Get(1,0); // 统计答案 
		
	for(int i=1;i<=n;i++){
		cout<<power[i]<<' ';
	}
	return 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
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

---

M题 Z-Game on grid / 网格上的Z-游戏

题目大意
Alice和Bob正在 $n\times m$ 的网格上玩游戏，其中每个单元格都有“A”、“B”或“.”写在上面。他们轮流在棋盘上移动棋子，爱丽丝先移动。
最初，棋子位于单元（1,1）上。在每个玩家的回合中，他或她可以将棋子向右或向下移动一个单元格，只要它不超出网格。
在任何时候，如果棋子在带有“A”的单元格中，爱丽丝获胜，游戏结束。如果棋子在带有“B”的单元格中，则鲍勃获胜，游戏结束。如果棋子到达单元格（n，m）而游戏未结束，则为平局。
问Alice是否总能找到赢得比赛、平局或输掉比赛的方法。

考察内容
动态规划

分析

状态：
$f[1][i][j]$ 表示考虑 $i,j$ 右下角的格子时的答案 $1$ （能不能赢）
$f[2][i][j]$ 表示考虑 $i,j$ 右下角的格子时的答案 $2$ （能不能平局）
$f[3][i][j]$ 表示考虑 $i,j$ 右下角的格子时的答案 $3$ （能不能输）

边界：
右下角

if(s[n-1][m-1]=='A'){
	f[1][n-1][m-1]=1; // 可以赢 
}
else if(s[n-1][m-1]=='.'){
	f[2][n-1][m-1]=1; // 可以平局 
}
else{ // 'B'
	f[3][n-1][m-1]=1; // 可以输 
}
1
2
3
4
5
6
7
8
9

转移：
从右下角倒着转移回左上角。轮到Alice移动时取max，轮到Bob移动时取min。

完整代码：

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=505;
ll n,m;
string s[N];
int f[4][N][N]; // f[1][i][j]表示考虑i,j右下角时的答案1
 
int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=0;i<n;i++){
			cin>>s[i];
		}
		for(int i=1;i<=3;i++){
			for(int j=0;j<=n;j++){
				for(int k=0;k<=m;k++){
					f[i][j][k]=0; // 初始化 
				}
			}
		}
		
		if(s[n-1][m-1]=='A'){
			f[1][n-1][m-1]=1; // 可以赢 
		}
		else if(s[n-1][m-1]=='.'){
			f[2][n-1][m-1]=1; // 可以平局 
		}
		else{ // 'B'
			f[3][n-1][m-1]=1; // 可以输 
		}
		
		// 转移f[1][j][k]，是否能赢 
		for(int j=n-1;j>=0;j--){
			for(int k=m-1;k>=0;k--){
				if(j==n-1 && k==m-1)continue;
				 
				if(s[j][k]=='A'){
					f[1][j][k]=1; 
				}
				else if(s[j][k]=='B'){
					f[1][j][k]=0; 
				}
				else{ // '.'
					if((j+k)%2==0){ // 轮到Alice走 
						if(j+1<=n-1)f[1][j][k]=max(f[1][j][k],f[1][j+1][k]);
						if(k+1<=m-1)f[1][j][k]=max(f[1][j][k],f[1][j][k+1]);
					}
					else{ // 轮到Bob走
						f[1][j][k]=1;
						if(j+1<=n-1)f[1][j][k]=min(f[1][j][k],f[1][j+1][k]);
						if(k+1<=m-1)f[1][j][k]=min(f[1][j][k],f[1][j][k+1]);
					}
				}
			}
		}
		
		// 转移f[3][j][k]，是否能输 
		for(int j=n-1;j>=0;j--){
			for(int k=m-1;k>=0;k--){
				if(j==n-1 && k==m-1)continue;
				
				if(s[j][k]=='A'){
					f[3][j][k]=0; 
				}
				else if(s[j][k]=='B'){
					f[3][j][k]=1; 
				}
				else{ // '.'
					if((j+k)%2==0){ // 轮到Alice走 
						if(j+1<=n-1)f[3][j][k]=max(f[3][j][k],f[3][j+1][k]);
						if(k+1<=m-1)f[3][j][k]=max(f[3][j][k],f[3][j][k+1]);
					}
					else{ // 轮到Bob走
						f[3][j][k]=1;
						if(j+1<=n-1)f[3][j][k]=min(f[3][j][k],f[3][j+1][k]);
						if(k+1<=m-1)f[3][j][k]=min(f[3][j][k],f[3][j][k+1]);
					}
				}
			}
		}
		
		// 转移f[2][j][k]，是否能平局 
		for(int j=n-1;j>=0;j--){
			for(int k=m-1;k>=0;k--){
				if(j==n-1 && k==m-1)continue;
				
				if(s[j][k]=='A'){
					f[2][j][k]=0; 
				}
				else if(s[j][k]=='B'){
					f[2][j][k]=0; 
				}
				else{ // '.'
					if((j+k)%2==0){ // 轮到Alice走
						if(j+1<=n-1)f[2][j][k]=max(f[2][j][k],f[2][j+1][k]);
						if(k+1<=m-1)f[2][j][k]=max(f[2][j][k],f[2][j][k+1]);
					}
					else{ // 轮到Bob走
						f[2][j][k]=1;
						if(j+1<=n-1)f[2][j][k]=min(f[2][j][k],f[2][j+1][k]);
						if(k+1<=m-1)f[2][j][k]=min(f[2][j][k],f[2][j][k+1]);
					}
				}
			}
		}
		
		if(f[1][0][0])cout<<"yes "; // 可以赢 
		else cout<<"no ";
		if(f[2][0][0])cout<<"yes "; // 可以平局 
		else cout<<"no ";
		if(f[3][0][0])cout<<"yes"<<endl; // 可以输 
		else cout<<"no"<<endl;
	}
	return 0;
}
/*
1
1 4
...B

1
3 3
..B
..B
BB.

1
3 4
.A..
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
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

---

进阶题

A题 Array / 数组

题目大意
给定一个数组 $a_1,...,a_n$ ，满足 $\sum \frac{1}{a_i}\le \frac{1}{2}$ 。

找出 $m$ 个整数 $c_0,...,c_i$ 来构造一个无限序列 $b$ ，其中 $b_i=c_{i\mathrm{mod}m}$ ， $b$ 中每隔 $a_i$ 个数至少出现一次 $i$ 。

考察内容
数学知识，排序，暴力，哈夫曼树

分析

解法一：
把每个 $a_i$ 改成小于他的最大的 $2$ 的幂（high_bit），因为原先倒数和小于等于 $\frac{1}{2}$，所以修改之后倒数和小于等于 $1$ 。之后按照哈夫曼树合并。

解法二：
按照 $a$ 从小到大排序，然后每隔 $a[i]$ 个直接填下标。填完剩下的放1。

#include
using namespace std;
int n,ans[1000005],m;
pair<int,int>a[100005];
int main(){
	// 读入 
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].first);
		a[i].second=i; // 记录下标 
	}
	sort(a+1,a+1+n); // 从小到大排序 
	
	// 填数字 
	m=1e6; // 足够大 
	for(int i=1,b=1;i<=n;b++,i++){
		while(ans[b]!=0)b++; // 找到第一个没填的位置 
		
		for(int j=b;;j+=a[i].first){ // 每隔a[i]个填一次 
			while(j>m || ans[j]!=0)j--; // 保证不越界且没填 
			
			ans[j]=a[i].second; // 填上下标 
			if(m-j+b<=a[i].first)break; 
		}
	}
	
	// 输出答案 
	printf("%d\n",m);
	for(int i=1;i<m;i++){
		printf("%d ",ans[i]?ans[i]:1);
	}
	printf("%d\n",ans[m]?ans[m]:1);
}
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

---