A.Two Rival Students
小的位置向左走，大的位置向右走直到走到最左或最右端或者x为0。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,x,a,b;
scanf("%d%d%d%d",&n,&x,&a,&b);
if(a>b)
swap(a,b);
while(x>0&&a>1)
x--,a--;
while(x>0&&b<n)
x--,b++;
printf("%d\n",b-a);
}
return 0;
}B.Magic Stick
贪心，如果是x偶数就乘3/2,如果是奇数就减一，直到当前的数大于等于y,则可以得到y.如果操作的过程中x的值重复出现，则不能得到y.
#include <bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
mp.clear();
int a,b;
scanf("%d%d",&a,&b);
while(a<b)
{
if(a&1)
a--;
else
a=a/2*3;
if(mp[a])
break;
mp[a]=1;
}
if(a>=b)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}C. Dominated Subarray
题目可以转化为求出现重复数字的最短区间，然后就是尺取裸题
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int a[maxn];
int n;
int cnt[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(cnt,0,sizeof(cnt));
int n;
scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
int l = 1;
int r = 2;
int ans=1e9;
cnt[a[l]]=1;
while(1)
{
while(r<=n)
{
if(!cnt[a[r]])
cnt[a[r]]=1;
else{
cnt[a[r]]++;
break;
}
r++;
}
if(r>n)
break;
while(cnt[a[l]]!=2){
cnt[a[l]]--,l++;
}
cnt[a[l]]--;
l++;
r++;
ans=min(ans,r-l+1);
}
if(ans!=1e9)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}D. Yet Another Monster Killing Problem
首先想到每一次应该选择可以杀最多怪物的英雄上。维护当天能杀大于等于c个怪物的英雄最强的战斗力，然后用ST表维护怪物战斗力的区间最大值，每次二分求当天能杀的怪物个数。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int bin[20];
int Log[maxn];
int mx[20][maxn];
int bit[maxn];
int n;
int a[maxn];
void update(int x,int id)
{
while(id){
bit[id]=max(bit[id],x);
id-=id&-id;
}
}
int query(int id)
{
int ans=0;
while(id<=n)
{
ans=max(ans,bit[id]);
id+=id&-id;
}
return ans;
}
void ST(int n)
{
for(int i=1;i<=n;i++)
mx[0][i]=a[i];
for(int i=1;i<=Log[n];i++)
for(int j=1;j<=n;j++)
if(j+bin[i]-1<=n)
mx[i][j]=max(mx[i-1][j],mx[i-1][j+bin[i-1]]);
}
int query(int x,int y)
{
int t=Log[y-x+1];
return max(mx[t][x],mx[t][y-bin[t]+1]);
}
int main()
{
int t;
scanf("%d",&t);
bin[0]=1;
for(int i=1;i<20;i++)
bin[i]=bin[i-1]*2;
Log[0]=-1;
for(int i=1;i<=200000;i++)
Log[i]=Log[i/2]+1;
while(t--)
{
int mmx=0;
scanf("%d",&n);
for(int i = 0;i <= n;++i)
bit[i]=0;
for(int i = 1;i <= n;++i)
scanf("%d",&a[i]),mmx=max(mmx,a[i]);
ST(n);
int m;
scanf("%d",&m);
int mmx2=0;
while(m--)
{
int x,c;
scanf("%d%d",&x,&c);
mmx2=max(mmx2,x);
update(x,c);
}
if(mmx2<mmx)
{
printf("-1\n");
continue;
}
int now = 1;
int ans=0;
bool ok=true;
while(now<n)
{
int l = now+1,r = n;
while(l<=r)
{
int mid=l+r>>1;
int tmp=query(now,mid);
int c = mid-now+1;
int you=query(c);
if(you>=tmp)
l = mid+1;
else
r = mid-1;
}
int d = l-1;
now = d+1;
ans++;
}
if(now==n)
ans++;
printf("%d\n",ans);
}
return 0;
}E. The Contest
比赛的时候没往DP去想，赛后看到题目标签才发现是一个挺显然的DP.dp[i][j]表示把i放在第j行时最小需要的操作步骤,先预处理出1-n的初始位置belong[i],转移方程:
dp[i][1]=dp[i-1][1]+(belong[i]!=1);
dp[i][2]=min(dp[i-1][1],dp[i-1][2])+(belong[i]!=2);
dp[i][3]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]))+(belong[i]!=3);#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int dp[maxn][4];
int a[maxn],b[maxn],c[maxn];
int belong[maxn];
int main()
{
int n;
int aa,bb,cc;
scanf("%d%d%d",&aa,&bb,&cc);
n=aa+bb+cc;
for(int i = 1;i <= aa;++i)
scanf("%d",&a[i]),belong[a[i]]=1;
for(int i = 1;i <= bb;++i)
scanf("%d",&b[i]),belong[b[i]]=2;
for(int i = 1;i <= cc;++i)
scanf("%d",&c[i]),belong[c[i]]=3;
dp[1][1]=1;
dp[1][2]=1;
dp[1][3]=1;
dp[1][belong[1]]=0;
for(int i = 2;i <= n;++i)
{
dp[i][1]=dp[i-1][1]+(belong[i]!=1);
dp[i][2]=min(dp[i-1][1],dp[i-1][2])+(belong[i]!=2);
dp[i][3]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]))+(belong[i]!=3);
}
printf("%d\n",min(dp[n][1],min(dp[n][2],dp[n][3])));
return 0;
}F.Make Them Similar
先枚举x的前15位，用vector储存相邻两个数与x异或后的0的个数的差，再枚举后15位进行同样的操作，最后枚举前15位的差分数组，查询后15位里有没有与它相反的数组(这里可以用map)。
#include <bits/stdc++.h>
using namespace std;
int a[105];
vector<int>v[32770];
map<vector<int>,int>mp;
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
int x = 0;
int last;
for(int i = 0;i < (1<<15);++i)
{
int tmp;
for(int j = 1;j <= n;++j)
{
tmp = a[j]^i;
int cnt=0;
for(int k = 0;k < 15;++k)
if((1<<k)&tmp)
cnt++;
if(j==1)
v[i].push_back(0);
else
v[i].push_back(cnt-last);
last=cnt;
}
}
vector<int>t;
for(int i = 0;i < 1<<15;++i)
{
int ii = i;
ii<<=15;
t.clear();
int tmp;
for(int j = 1;j <= n;++j)
{
tmp = a[j]^ii;
int cnt=0;
for(int k = 15;k < 30;++k)
if((1<<k)&tmp)
cnt++;
if(j==1)
t.push_back(0);
else
t.push_back(cnt-last);
last=cnt;
}
mp[t]=ii;
}
for(int i = 0;i < (1<<15);++i)
{
vector<int>p;
for(int j = 0;j < v[i].size();++j)
p.push_back(-v[i][j]);
if(mp[p])
{
int ans=i+mp[p];
printf("%d\n",ans);
return 0;
}
}
printf("-1\n");
return 0;
}