A题
题意：
给出a,b（$ a,b \lt 10^{18} $），有两种操作：1、a,b加一 2、a,b减一（a,b非负），求最大的gcd(a,b)
题解：
对于gcd(a,b)，有$gcd(a,b) \lt |a-b|$，所以第一问的答案就是ans1=|a-b|，对于第二问，最少操作步数是向上或向下将a，b均调整至ans1倍数的最少步数（当然包含将其中一个调整至0），若a=b，答案为inf
代码：
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int t;
signed main(){
scanf("%lld",&t);
for(int i=1;i<=t;i++){
int a,b;
scanf("%lld %lld",&a,&b);
if(a==0||b==0){
printf("%lld %lld\n",max(a,b),min(a,b));
}
else if(a==b){
printf("0 0\n");
}
else{
int ans1=max(a,b)-min(a,b);
int ans2=min(a,b);
int upa = (a/ans1+(a%ans1!=0));
int delta1a = upa*ans1-a;
int upb = (b/ans1+(b%ans1!=0));
int delta1b = upb*ans1-b;
if(delta1a==delta1b){
ans2=min(ans2,delta1a);
}
upa = (a/ans1);
delta1a = a-upa*ans1;
upb = (b/ans1);
delta1b = b-upb*ans1;
if(delta1a==delta1b){
ans2=min(ans2,delta1a);
}
printf("%lld %lld\n",ans1,ans2);
}
}
return 0;
}
|
B题
题意：
给你一个数组${a}$，你可以执行任意次操作，每次将使一个数减一，另一个数加一，要求使
最小
题解：
容易想到，这样的操作的结果是使得{a}在总和不变的情况下，改变$a_i$的值，令元素间差最小。
最终答案的形态一定是$x\ x\ x\ x\ x \dots\ x\ x+1\ x+1$
相同元素间贡献为0，不相同元素贡献为1，所以可以直接O(n)求出答案
代码：
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
int a[200200],sum,remain;
void work(){
sum=0;
remain=0;
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
}
remain = sum%n;
int ans1=0;
for(int i=1;i<=n;i++){
if(i<=remain){
ans1+=n-remain;
}
else{
ans1+=0;
}
}
printf("%lld\n",ans1);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--){
work();
}
return 0;
}
|
C题
题意：
给你三张卡片，抽到概率分别为c,m,p，当抽到第三张时游戏停止，否则，如果当前卡片绸带概率小于a，将其减为0，否则减去v（$v \gt 0.1$），概率平均分给其他卡片，问期望游戏进行几轮
题解：
注意到v最少为0.1，故游戏最多进行10轮左右，爆搜一发即可
代码
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
double eps = 10e-6;
double dfs(double c,double m,double p,double v){
double ans=0.0;
if(fabs(c)>eps){
if(c-v>eps){
if(fabs(m)>eps)
ans+=c*(dfs(c-v,m+v/2.0,p+v/2.0,v)+1);
else
ans+=c*(dfs(c-v,0,p+v,v)+1);
}
else{
if(fabs(m)>eps)
ans+=c*(dfs(0,m+c/2.0,p+c/2.0,v)+1);
else
ans+=c*(dfs(0,0,p+c,v)+1);
}
}
if(fabs(m)>eps){
if(m-v>eps){
if(fabs(c)>eps)
ans+=m*(dfs(c+v/2.0,m-v,p+v/2.0,v)+1);
else
ans+=m*(dfs(0,m-v,p+v,v)+1);
}
else{
if(fabs(c)>eps)
ans+=m*(dfs(c+m/2.0,0,p+m/2.0,v)+1);
else
ans+=m*(dfs(0,0,p+m,v)+1);
}
}
if(fabs(p)>eps){
ans+=p*1;
}
return ans;
}
int main(){
int T;
scanf("%d",&T);
for(int i=1;i<=T;i++){
double C,M,P,V;
scanf("%lf %lf %lf %lf",&C,&M,&P,&V);
printf("%.12lf\n",dfs(C,M,P,V));
}
return 0;
}
|
D1题
题意：
交互题，定义k进制下的a XOR b为(a+b)%MOD k，给出一个在0~n-1范围内的数x，每次询问一个y，如果y=x，则猜对答案，结束，否则将x变为z，z满足$x \oplus_k z = y$，限制询问次数为n次
简化条件：k=2
题解：
由于k=2，问题被简化成了按位异或，由于能询问N次，所以我们肯定是从0询问到N-1，但是如果这次错误了，x就变成$y\oplus x$了，所以为了避免前面猜错的影响，第1次询问应该询问0，而i次询问应该询问i^(i-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
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void work(){
int n,k;
scanf("%d %d",&n,&k);
int last=0;
for(int i=0;i<n;i++){
printf("%d\n",last^i);
fflush(stdout);
last=i;
int r;
scanf("%d",&r);
if(r==1){
return;
}
else if(r==0){
continue;
}
else{
return;
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
work();
}
return 0;
}
|
D2题
题意：
和D1基本相同，只不过K的范围为[2,100]
题解：
首先把输入的10进制数转化为k进制，然后从0~n-1开始询问，但是注意这次消除影响的方式不同，考虑原来答案k进制数为$ a_1 a_2 a_3 a_4 $，询问为$b_1b_2b_3b_4$，询问后会是$(b_1-a_1)(b_2-a_2)(b_3-a_3)(b_4-a_4)$，下次猜测是$c_1c_2c_3c_4$，实际询问应当询问$(b_1-c_1)(b_2-c_2)(b_3-c_3)(b_4-c_4)$，这样的话询问后会是$(a_1-c_1)(a_2-c_2)(a_3-c_3)(a_4-c_4)$
按照相同思路处理即可
代码：
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k;
struct Num{
char arr[20];
char cnt;
Num(int x){
for(int i=0;i<20;i++)
arr[i]=0;
cnt=0;
while(x>0){
arr[cnt]=x%k;
cnt++;
x/=k;
}
}
Num(const Num& t){
for(int i=0;i<20;i++)
arr[i]=0;
cnt=t.cnt;
for(int i=0;i<t.cnt;i++)
arr[i]=t.arr[i];
}
Num Xor(const Num &t){
Num ans(0);
ans.cnt = max(cnt,t.cnt);
for(int i=0;i<ans.cnt;i++){
ans.arr[i]=(arr[i]+t.arr[i])%k;
}
return ans;
}
Num dec(const Num &t){
Num ans(0);
ans.cnt = max(cnt,t.cnt);
for(int i=0;i<ans.cnt;i++){
ans.arr[i]=(arr[i]-t.arr[i]+k)%k;;
}
return ans;
}
int out(void){
int ans=0;
int base=1;
for(int i=0;i<cnt;i++){
ans+=base*arr[i];
base=base*k;
}
return ans;
}
};
void work(){
scanf("%d %d",&n,&k);
int f=0;
Num last(0);
for(int i=0;i<n;i++){
Num now(i);
Num ans(0);
if(!f)
ans=now.dec(last);
else
ans=last.dec(now);
f^=1;
printf("%d\n",(ans).out());
fflush(stdout);
last=now;
int r;
scanf("%d",&r);
if(r==1){
return;
}
else if(r==0){
continue;
}
else{
return;
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
work();
}
return 0;
}
|
E题
题意：
给出一个n次超立方体，标准的生成n次超立方体的方法
给出一个编号为$[0,2^{n-1}]$的n-1次超立方体和编号为$[2^{n-1}+1,2^n]$，将i与$ 2^{n-1}+i $连边，就可以构造出n次超立方体
题目有两问，第一问：给出超立方体之间的点的相邻关系，求一个排列P，让标准超立方体的标号在被P映射后符合给出的相邻关系
第二问：给出n种颜色，求一种涂色方案，让超立方体的每个顶点都能访问到所有颜色
题解：
标准超立方体有这样的性质：
两个相邻节点只有一个二进制位不同
每个节点都有n个相邻节点
不存在三角形（这样至少两个二进制位不同）
第一问：
由于所有的顶点都等价，所以可以钦定0号节点对应一个节点，然后从1号节点开始求解，对当前的i号节点，找到和i相连的n个节点，这n个节点中已经确定好了k个节点，从这k个节点对应的编号中，找出与这些编号都相连的最小的节点，即为i号对应的节点
可行性的证明：
假设当前要求解的节点是i，i的二进制结构是$s_1us_2vs_3$，考虑于其相连的两个节点，则和u相连的节点v1，v2只有$s_1u’s_2vs_3$和$s_1us_2v’s_3$两种组成，他们同时相连的还有另一种节点$s_1us_2vs_3$。如果我们按照0~i的顺序处理，只考虑已经确定的节点，那么uv只能同时为0或1，否则v1，v2会大于u。那么设u < v，因为u < v1，u < v2 ，所以u一定是被计算过的，所以只剩一种选择
第二问：
给出这样一个构造，对于节点i，i的二进制表示为$b_1b_2b_3b_4\dots b_n$，i的颜色为$ b_1*c_1 \oplus b_2*c_2 \dots $ ，如果想要从颜色为$i_c$的i访问颜色c，访问节点$ i\oplus(1<<(c\oplus i_c)) $即可
构造可行的说明：
由于通过p可以映射，所以只需要证明对标准情况可用即可
从每个节点，如果要前往颜色k，则可以通过两种颜色异或得到不同的二进制位的位置，直接访问即可
代码
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
int P[(1<<16)],cx[(1<<16)];
bool vis[(1<<16)];
vector<int> G[(1<<16)];
set<int> S[16];
void work(){
int n;
scanf("%d",&n);
for(int i=1;i<=n*(1<<(n-1));i++){
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
P[0]=0;
vis[P[0]]=true;
for(int u=1;u<(1<<n);u++){
for(int i=0;i<n;i++)
S[i].clear();
int tmp=0;
for(int i=0;i<n;i++){
int v=u^(1<<i);
if(v<u){
for(int j=0;j<G[P[v]].size();j++){
if(!vis[G[P[v]][j]])
S[i].insert(G[P[v]][j]);
}
}
}
set<int> s,ttmp;
s.clear();
for(int i=0;i<n;i++){
if(!s.size()){
s=S[i];
continue;
}
if(S[i].size()){
ttmp.clear();
set_intersection(s.begin(),s.end(),S[i].begin(),S[i].end(),inserter(ttmp,ttmp.begin()));
s=ttmp;
}
}
P[u]=*(s.begin());
vis[P[u]]=true;
}
for(int i=0;i<(1<<n);i++)
printf("%d ",P[i]);
printf("\n");
if((n&(-n))!=n)
printf("-1\n");
else{
for(int i=0;i<(1<<n);i++){
int c=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
c^=j;
}
}
cx[P[i]]=c;
}
for(int i=0;i<(1<<n);i++){
printf("%d ",cx[i]);
}
printf("\n");
}
for(int i=0;i<(1<<n);i++){
cx[i]=P[i]=vis[i]=0;
G[i].clear();
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
work();
}
return 0;
}
|