A. 来自瑞思拜龙的善意

因为对于任何$1≤i,j≤n$，都有 $1≤S\%m≤n$ 。

可以发现，当$i$取1的时候，$S$ 可能为$[1,n]$的任何数，因为$S\%m\ne0$，所以如果$m$存在，$m$一定大于$n$并且$m$一定为质数，即$m$不存在在$[1,n]$的因子。

那么可以简单猜测一下，$m$为大于$n$的第一个质数。

再来，当$n+1$不为质数时，那么在$[1, n]$必存在一对$(i, j)$为$n+1$的因子，此时$S = i * j = n + 1,S\%m = (n + 1) > n$，不满足题意，因此，只有当$(n+1)$为质数时，$m$存在，为$n+1$。

注意$n=1$有任何解。

因为题面的$n$很小，直接判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int check(int num){
    int n = sqrt(num);
    for(int i = 2; i <= n;i++){
        if(num % i == 0)return 0;
    }
    return 1;
}
int main(void){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(check(n+1)) cout<<n+1<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

B. 校园跑

B题是一个倍增。

可以发现，每个点只有一个下节点，那么说明，从每个点开始走$1$步，走$2$步，走$n$步都是固定的一个数值，并且都是一个固定的目标，那么我们可以用倍增的思想，记录从当前点开始走$2^0$,$ 2^1$, $2^2$, …，$2^{32}$有多远，以及目标点。然后将$n$拆成一个二进制数直接一位一位找，走到目标点再用剩下的步数找，最终步数用完了也就走完了。

dis[i][32]：从i开始出发走$2^n$次方步的距离

aim[i][32]：从i开始出发走$2^n$次方步的目标

因为最开始给的是从每个点开始走一步的距离和目标，从$2^0$步可以得到$2^1$步，然后可以得到$2^2$步，由此下去就可以得到$2^{32}$步，所以只需要32次for循环即可处理出每个点的信息。然后和快速幂一样的方法就可以算出答案。

注意要开long long，得到答案的时候点要动。

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 <iostream>
using namespace std;
#define ll long long
const int maxn = 1e5+5;
ll dis[maxn][35];
ll aim[maxn][35];
ll ans[maxn];
inline void init(int n){
    for(int k = 1;k <= 32;k++){
        for(int i = 1;i <= n;i++){
            dis[i][k] = dis[i][k-1] + dis[aim[i][k-1]][k-1];//两个半步合成一个大步
            aim[i][k] = aim[aim[i][k-1]][k-1];//两个小目标变成一个大目标
        }
    }
}
inline ll getdis(int now, ll k){
    ll ans = 0;
    ll num = 0;
    while(k){
        if(k & 1) {
            ans += dis[now][num];//遇到1就走
            now = aim[now][num];//更新走了之后的位置
        }
        num++;
        k>>=1;
    }
    return ans;
}
signed main(void){ 
    ll n, m;
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        cin>>aim[i][0];
    }
    for(int i = 1;i <= n;i++){
        cin>>dis[i][0];
    }
    init(n);
    ll maxx = 0;
    for(int i = 1;i <= n;i++){
        ans[i] = getdis(i, m);
        maxx = max(maxx, ans[i]);
    }
    for(int i = 1;i <= n;i++){
        if(ans[i] == maxx){
            cout<<i<<" ";
        }
    }
    puts("");
    cout<<maxx;
    
    return 0;
}

C. CUIT_WIFI咋又断啦！！！

因为本题的数据范围为int以内，所以答案也不会超过int的范围，而且两个数组都是有序的，所以可以直接二分。假定答案的上界为$10^{10}$（或更大），那么对于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
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=2000005;
long long n,m,a[N],b[N],ans=0;
long long efl(int x)
{
	long long l=1,r=m,ans=-1e10;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		if(b[mid]<=x)
			l=mid+1,ans=b[mid];
		else
			r=mid-1;
	}
	return ans;
}
long long efr(int x)
{
	long long l=1,r=m,ans=1e10;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		if(b[mid]>=x)
			r=mid-1,ans=b[mid];
		else
			l=mid+1;
	}
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)
		scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++)
		ans=max(ans,min(a[i]-efl(a[i]),efr(a[i])-a[i]));//,cout<<efl(a[i])<<endl;
	printf("%lld",ans);
	return 0;
}

然而还有双指针做法，定义$l，r$两个边界指针，用$res$维护最小费用，然后往后滚就能得到答案了。

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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int n, m;

int main(void){
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];

    int res = 0;
    for (int i = 0, j = 0; i < n; ++i)
    {
        // 在b中找到第一个大于等于 a[i]的数
        while (j < m && b[j] < a[i]) j ++;

        if (j == 0)         // b[0] >= a[i]
        {
            res = max(res, b[0] - a[i]);
        }
        else if (j == m)    // b[m - 1] < a[i]
        {
            res = max(res, a[i] - b[m - 1]);
        }
        else                // b[j] >= a[i] > b[j - 1]
        {
            res = max(res, min(b[j] - a[i], a[i] - b[j - 1]));
        }
    }

    cout << res << endl;
    return 0;
}

D. Make them the same(easy)

简单的构造题，移项化简即可

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main(void){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<n<<"/"<<n-1<<endl;
    }
    return 0;
}

E. Make them the same(hard)

稍稍复杂一点的构造，可以找到特解

我们令前$n-2$个全为1，第$n-1$个为$2$，然后设第$n$个为未知数$a_n$，即可解出$a_n$。

当$n=1，2$时需要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main(void){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(n == 1) puts("1");
        else if(n == 2)puts("2 2");
        else {
            for(int i = 0;i < n-2;i++) {cout<<"1 ";}
            cout<<"2 "<<n<<endl;
        }
    }
    return 0;
}

F. 这不是一道物理题

题意：有一连串的开关，按当前开关会使当前及其相邻的开关改变状态（0到1，1到0），并且灯泡也会改变状态（亮到熄，熄到亮），给出最终开关状态，问最终灯泡的熄亮或开关状态无法实现。

暴力

观察可以发现，如果连续按动相邻的两个开关，其实是相当于将左侧的1移动要右侧去了，例如1000，按动2号与3号开关，就变成了0001，那么按此规律，我们可以从左侧遍历，将所有的1移动到右边去，然后最右边只剩下长度为2的01串。然后再来判断这个01串消除的次数，如果不能消除则将其全部挪到左边去再来判断一次即可。如果都不能则不能形成。

注意挪动的时候是按了两个连续的开关，因此灯泡的状态并没有改变。

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
#include<iostream>
using namespace std;
int main(void){
    int t;
    cin>>t;
    while(t--){
      int n;
      cin>>n;
      string str;
      cin>>str;
      if(n == 2){//1，2特判
        if(str[0] == str[1]){
          if(str[0] == '1') puts("1");
          else puts("0");
        }else{
          puts("-1");
        }
        continue;
      }else if(n == 1){
        if(str[0] == '1') puts("1");
        else puts("0");
        continue;
      }
      for(int i = 0; i< n;i++) str[i] -= '0';
      for(int i = 0;i < n-2;i++){//往右挪
        if(str[i] == 1){
          str[i] ^= 1;
          if(i + 3 < n) str[i+3] ^= 1;//把1向右挪三为
        }
      }
      if(str[n-1] == str[n-2]){//对剩下的部分分别判断
        if(str[n-1] == 1) puts("1");
        else puts("0");
      }else{
        if(n%3 == 0){
          if(str[n-1] == 1) puts("0");
          else puts("1");
        }else if((n-1) % 3 == 0){
          if(str[n-2] == 1) puts("0");
          else puts("1");
        }else{
          puts("-1");
        }
      }
    }
    return 0;
}

解异或方程

注意，因为按一次会影响左边，当前，右边三个开关（两头除外）。那么反过来想，一个开关的状态只与左边，当前，右边三个开关是否按了有关，而状态只有两种，即三个开关中为1的数量对2模除就为当前开关的状态，超过1模2，即为异或，即可以得到异或方程。($\bigoplus$为异或运算)

设每个开关是否按了为$S_n$，最终状态为$a_n$，那么$an = Sn-1 \bigoplus Sn \bigoplus Sn+1$，如下

题目给出的是$a_n$的串，那么可以设出一个$n$元一次方程组，有唯一解。解出来的$S_n$为$1$，即为哪些开关按了，有偶数个1即按了偶数次，此时灯是熄的，否则灯是亮的，如果无解则无法到达该状态。因为方程的解一定是0和1的串，那么我们可以令$S_1$为$0$与$1$分别去check，如果能行即为正确答案，如果都不行那么无解。注意方程有唯一解，所以不存在为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
#include <iostream>
using namespace std;

inline int check(string str){
    int len = str.length();
    int ans = 0;
    int la, now, next;
    la = 0; now = 1; next = 0;//令当前为1来试试
    for(int i = 0;i < len-1;i++){
        if(now == 1) ans++;//记录1的个数
        next = ((str[i] - '0') ^ now ^ la);//由异或的逆运算
        la = now; now = next; next = 0;
        
    }
    if(now == 1) ans++;
    if((la ^ now ^ next) == (str[len-1] - '0')) return (ans & 1);
   
    ans = 0;
    la = 0; now = 0; next = 0;//令当前为0来试试
    for(int i = 0;i < len-1;i++){
        if(now == 1) ans++;
        next = ((str[i]-'0') ^ now ^ la);
        la = now; now = next; next = 0;
        
    }
    if(now == 1) ans++;
    if((la ^ now ^ next) == (str[len-1] - '0')) return (ans & 1);
    return -1;//如果都不行那么无解
}
signed main(void){ 

    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string a;
        cin>>a;
        int ans = check(a);
        cout<<ans<<endl;
    }

    return 0;
}

G. 忙碌的大学生活

这个题解法极其多，因为他是一个有向无环图，数据也小，直接干就行。

先初始化dp[i] = i，即默认没有捷径，然后有了捷径，可得转移方程。

dp[i] = min(dp[i], dp[i-1]+1); 当前点可以从上一个点走过来。

dp[ai] = min(dp[ai], dp[i]+1); 可以走捷径或者不走捷径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int dp[1005];
int a[1005];
int main(void){
        int n;
        cin>>n;
        for(int i = 1; i <= n;i++){
            dp[i] = i;
            cin>>a[i];
        }
        for(int i = 1;i <= n;i++){
            dp[i] = min(dp[i], dp[i-1]+1);//当前点可以从上一个点走一部
            dp[a[i]] = min(dp[a[i]], dp[i]+1);//捷径目标点可以选择走不走捷径
        }
        for(int i = 1;i <= n;i++){
            cout<<dp[i]<<" ";
        }
        cout<<endl;
    return 0;
}

H. Bang Bang Keli Ba

”原“题，原味极重。

这个题直接贪心即可，因为要$b$数组非递减，$c$数组非递增，那么我们可以默认$b$数组当前元素与上一个元素相同，然后来匹配$c$数组即可，如果算出来满足不了$c$，那么就调整一下当前的$b$使$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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long Num[500005],Num1[500005],Num2[500005];
int main(void)
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%lld",&Num[i]);
	Num1[0]=Num[0];
	Num2[0]=0;//初始化两个数列的第一个 
	for(int i=1;i<n;i++)
	{
		if(Num[i]>=Num[i-1])//此时该数比上一个大（或相同），可以将递增的数列增加而递减的数列保持不变 
		{
			Num2[i]=Num2[i-1];
			Num1[i]=Num[i]-Num2[i];//可以写成 Num1[i]+=(Num[i]-Num[i-1]); 
		}
		else//同理，可以将递减的数列减少而递增的数列保持不变 
		{
			Num1[i]=Num1[i-1];
			Num2[i]=Num[i]-Num1[i];//可以写成 Num2[i]+=(Num[i]-Num[i-1]); 
		}
	}
	for(int i=0;i<n-1;i++)//输出答案 
		printf("%lld ",Num1[i]);
	printf("%lld\n",Num1[n-1]);
	for(int i=0;i<n-1;i++)
		printf("%lld ",Num2[i]);
	printf("%lld",Num2[n-1]);
}

I. 啊,小兵的德芙被分食了

先让所有的都为$1$，那么就剩下了$n - m$块巧克力，那么我们先分1块出去，此时乘积为$1\times 1 \times …\times 2 = 2$，剩下$n - m - 1$，然后再来分。

那么下一块有两种放法，要么分到$1$里面去，要么分到$2$里面去，如果分到$1$里面去，那么会对乘积产生$1 \times 1 \times … \times 2 = 2$的增量，如果分到$2$里面去，那么只会产生$1 \times 1 \times .. \times 1=1$的增量，因此将下一块巧克力分到$2$里面去是最合理的，同理，将剩下的都分到一起去，此时乘积是最小的。

因此答案为$1\times 1 \times … \times (n - (m - 1)) = n - (m -1)$。

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main(void){
    int n, m;
    cin>>n>>m;
    cout<<n-(m-1)<<endl;
    return 0;
}

J. No Idea

真·No Idea，除了出题人没人会做系列。

直接给链接吧 https://www.cnblogs.com/xdaniel/p/15708490.html

K. 卷王之王

我们先来观察一下多次投掷会怎么样假设$k = 6$， $n = 3$

当投掷一次时此时，点数期望为

$n = 1 , \frac {(1 + 2+3+4+5+6)} {6} = 3.5$

那么投掷两次呢，如果我们投了一次，发现我再投一次期望更高，那么我肯定会选择再投一次，即用投一次的期望替换掉当前的点数，即

$n = 2,\frac {3.5 + 3.5 + 3.5+4+5+6}{6} = 4.25$

同理，投三次：

$n = 3,\frac {4.25+4.25+4.25+4.25+5+6}{6} = 4.666…$

可以发现，当投第$n$次的时候，如果当前对点数不满意，那么我们可以继续投$n-1$次，即用$n-1$的期望来替换掉比当前小的点数。

当$n=1$的时候是可以直接算出来的，那么只需要往后滚就可以算出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int k, n;
        cin >> k >> n;
        double ans = 0;
        while (n--)
        {
            int temp = (int)ans;
            double sum=ans;
            ans = (double)((double)temp * sum + (double)(temp + 1 + k) * (k - temp) / 2) / k;
        }
        printf("%.6f\n", ans);
    }
    return 0;
}

L. 拓展GCD

将原式化简，左边是个很明显的gcd

如果$k$有解，那么原式的$x,y$有解，当且仅当右边的和为偶数时$k$有整数解。

因为$a_i$与$a_j$都要同时除以$gcd(a_i, a_j)$，那么$\frac {a_i} {gcd(a_i, a_j)}, \frac {a_j} {gcd(a_i, a_j)}$必不可能为偶数，只能为奇数，而且必须除了$gcd(a_i, a_j)$之后同时为奇数。因此$a_i,a_j$中2的因子数必须相同，此时的$(a_i,a_j)$才是一个有效解。回到除法，当一个数字除$2$，即数字右移一位，那么因子$2$的个数即为数字二进制中右边第一个$1$后方有多少个$0$，统计$0$的个数，然后对于每一个$0$的数量都可以任选两个，$C_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
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll sum[32];

int getsum(int k)
{
	int res = 0;
	while(!(k&1))
	{
		res++;
		k>>=1;
	}
	return res;
}
int main()
{
	ll ans = 0;
	int n;
	scanf("%d",&n);
	ll tot = 0;
	for(int i = 0;i < n;i++)
	{
		int k;
		scanf("%d",&k);
		int s = getsum(k);
		sum[s]++;
		tot++;
		ans += sum[s]-1;
	}
	printf("%lld",ans);
    return 0;
}