题目链接：https://codeforces.com/contest/1110
A. Parity
题意：
给出{ak},b,k，判断a1*b^(k-1)+a2*b^(k-2)+...+ak*b^0的奇偶性。
题解：
暴力求模2意义下的值就好了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n;
int b,k;
int a[N];
ll qp(ll A,ll B){
ll ans = ;
while(B){
if(B&) ans=ans*A%;
A=A*A%;
B>>=;
}
return ans;
}
int main(){
cin>>b>>k;
for(int i=;i<=k;i++) scanf("%d",&a[i]);
int t=b%;
int sum = ;
for(int i=k-;i>=;i--){
sum=sum+a[k-i]*qp(t,i);
sum%=;
}
if(sum&) cout<<"odd";
else cout<<"even";
return ;
}
B. Tape
题意：
在[1,m]这个区间中，有n个点，现在要用k个木棍去覆盖完这些点，问最短覆盖长度为多少。
题解：
首先将起始点和终点间的距离求出来，然后考虑将不需要的一些覆盖给减去。
具体做法就是用优先队列保存两个相邻点之间的间隔，然后不断取最大的间隔减去，最后使得剩下的区间还剩下k个即可。
代码如下：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5+;
int n,m,k;
ll a[N],d[N];
ll ans;
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++) scanf("%I64d",&a[i]);
ans=a[n]-a[]+;
priority_queue <ll> q;
for(int i=;i<n;i++){
d[i]=a[i+]-a[i];
q.push(d[i]-);
}
int cnt = ;
while(cnt<k){
ll now = q.top();q.pop();
cnt++;
ans-=now;
}
cout<<ans;
return ;
}
C. Meaningless Operations
题意：
有多个询问，每次询问会输入一个数a，然后对于所有的数b(1<=b<a)，求max{ gcd(a&b,a^b) }。
题解：
这个可以打表来做。
如果想的话，就是分两种情况考虑：一种是所有二进制位数都为1，另一种就是并非这样。
第二种思考起来比较简单，答案肯定为2^x-1，我们取的b只需要刚好把a二进制中的0填补就行了。
第一种情况会有一个这样的性质：a&b+a^b=a。现在设g=gcd(a&b,a^b)，所以现在有g|a&b,g|a^b，那么自然有g|a。
我们会发现g其实为a的因子，那么这种情况找a的最大因子就好啦。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
ll a;
ll p2[];
ll Print(ll x){
for(ll i=;i*i<=x;i++){
if(x%i==){
return x/i;
}
}
return ;
}
int main(){
cin>>q;
p2[]=;
for(int i=;i<=;i++) p2[i]=p2[i-]*;
while(q--){
cin>>a;
int i;
for(i=;i>=;i--) if((<<i)&a) break ;
if(a&(a+)) cout<<p2[i+]-<<endl;
else cout<<Print(a)<<endl;
}
return ;
}
D. Jongmah
题意：
给出n个数，数的大小不超过m，问最多有多少个类似于(x,x,x),(x-1,x,x+1)这样的三元组，每个数最多用一次。
题解：
对于我这样的蒟蒻来说，dp方程式理解了很久，感觉十分巧妙。
首先，就是对于类似于(x-1,x,x+1)这样的三元组来说，我们只需要考虑不超过三个的情况就可以了。因为当其超过三个时，直接选(x,x,x)这种类型得到的答案是一样的。
设dp(i,j,k)的定义为：当前在i这个位置，有j个(i-1,i,i+1)三元组，有k个(i,i+1,i+2)这样的三元组。
转移的话就从(i-2,i-1,i),(i-1,i,i+1) (即i-1)转移过来，我们在计算的时候附加上(x,x,x)这种类型就好了。
因为每次都从i-1转移过来，所以还可以用滚动数组优化掉一维，但是不优化对于这题也没啥影响~
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+;
int n,m;
int a[N],dp[N][][];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
a[x]++;
}
for(int i=;i<=m;i++){
for(int j=;j<;j++){
for(int k=;k<;k++){
for(int l=;l<;l++){
if(l+j+k>a[i]) continue ;
dp[i][k][l]=max(dp[i][k][l],dp[i-][j][k]+l+(a[i]-l-k-j)/);
}
}
}
}
cout<<dp[m][][];
return ;
}
E. Magic Stones
题意：
给出两个数列{cn},{tn}，现在可以进行一些变化，比如对于ci来说，可以让ci=ci-1+ci+1-ci (2<=i<n)，变化的次数以及位置不限，问是否最后能得到t数列。
题解：
这题也比较巧妙吧，首先判断一下首尾可以知道是否可行。
之后根据这个式子，利用差分数组来解。
设di=ci+1-ci，那么当ci变化后，di=ci'-ci-1=ci+1-ci=di+1，di+1=di，也就是说，两个差分数组相当于换了下位置。
也就是说，题目中的操作，实质上是不断交换差分数组的位置。
之后就有很多种方法了，给出我的代码吧：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+;
int n;
ll c[N],t[N],d[N];
multiset <ll> s;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&c[i]);
for(int i=;i<=n;i++) scanf("%d",&t[i]);
if(c[]!=t[] || c[n]!=t[n]){
cout<<"No";
return ;
}
for(int i=;i<n;i++) d[i]=c[i+]-c[i],s.insert(d[i]);
for(int i=;i<=n;i++){
ll need = t[i]-t[i-];
auto it = s.lower_bound(need);
if(*it==need){
s.erase(it);
}else{
cout<<"No";
return ;
}
}
cout<<"Yes";
return ;
}
除开这种，还可以求出t数列的差分数组，然后对两个差分数组进行排序来比较，实现方法比我简单多了。