VK-Cup,cf里面只有切成俄文才能看到，题目也都是俄文的（百度翻译成英文和中文）.
两人组队参赛的，赛期1天，乐多赛赛制（和时间基本无关，交上去挂了扣分）。这次是第一场资格赛。
这次又和ditoly大佬组队啦，队名不知道该叫什么，因为我们真的菜，就取了个名字叫vegetable chicken（菜鸡）
但是题目不会很难，所以都一次过了（真的舒服）
-----------------------------------我是分割线
A.Год поступления в университет（我也不知道是什么啊，我也很绝望啊）
题意：有一个人参加了n(n<=5)个兴趣小组，然后它的入学年份和参加年份差距不会超过x（这东西不告诉你），求入学年份。
做题情况：根本看不懂题意，去问了学长才知道。
题解：最大值加最小值除2
ditoly的代码真的风骚
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,x,a=,b=;
for(cin>>n;n--;)cin>>x,a=max(a,x),b=min(b,x);
cout<<((a+b)>>);
}
B. Новость о зачёте(我要是知道这个是什么，我还会这么绝望吗？）
题意：有n个人，第一个人知道了一条消息，每个人最多发送ai条消息，你要让所有人都知道这个消息，求一个方案即可。
题解：贪心一下，每次发给能发最多消息的人。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define MAXN 600000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
}
int a[],n,cnt=;
int ans[][];
struct node{
int a,num;
friend bool operator< (node x,node y)
{
return x.a<y.a;
}
};
queue<int> q;
priority_queue<node> q2; int main()
{
n=read();for(int i=;i<=n;i++)a[i]=read();
for(int i=;i<=a[];i++)q.push();
for(int i=;i<=n;i++)q2.push((node){a[i],i});
while(!q.empty()&&n>)
{
int u=q.front();q.pop();
node v=q2.top();q2.pop();
ans[][++cnt]=u;ans[][cnt]=v.num;
for(int i=;i<=v.a;i++)q.push(v.num);
n--;
}
if(n!=) return *puts("-1");printf("%d\n",cnt);
for(int i=;i<=cnt;i++) printf("%d %d\n",ans[][i],ans[][i]);
return ;
}
C.Цикл в лабиринте（警察叔叔，就是它让我绝望的！）
题意：有一张网格图，有一些点是障碍，有一个机器人在某一个点，每次可以上下左右走，要走k次之后回到起点，求一个字典序最小(D,L,R,U)的方案6
n,m<=1000,k<=10^6
题解：bfs一下每个点到起点的最短距离，每次按字典序搜，能走就走。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
}
int n,m,x=,y=,k;
char s[][];
int d[][];
char ans[];
struct node{
int x,y;
}newx;
queue<node> q;
const int dis[][]={{,},{-,},{,},{,-}}; void bfs()
{
q.push((node){x,y});d[x][y]=;
while(!q.empty())
{
newx=q.front();q.pop();
for(int i=;i<;i++)
{
int xx=newx.x+dis[i][];
int yy=newx.y+dis[i][];
if(xx<||yy<||xx>n||yy>m||d[xx][yy]||s[xx][yy]=='*') continue;
d[xx][yy]=d[newx.x][newx.y]+;
q.push((node){xx,yy});
}
}
} int main()
{
n=read();m=read();k=read();
for(int i=;i<=n;i++)scanf("%s",s[i]+);
for(int i=;i<=n&&!x;i++)
for(int j=;j<=m&&!x;j++)
if(s[i][j]=='X')
{x=i;y=j;s[i][j]='.';}
bfs();
for(int i=;i<=k;i++)
{
if(x<n&&s[x+][y]=='.'&&d[x+][y]<=k-i+){ans[i]='D';++x;continue;}
if(y>&&s[x][y-]=='.'&&d[x][y-]<=k-i+){ans[i]='L';--y;continue;}
if(y<m&&s[x][y+]=='.'&&d[x][y+]<=k-i+){ans[i]='R';++y;continue;}
if(x>&&s[x-][y]=='.'&&d[x-][y]<=k-i+){ans[i]='U';--x;continue;}
return *puts("IMPOSSIBLE");
}
for(int i=;i<=k;i++)printf("%c",ans[i]);
return ;
}
D.
给定n个数和k，求有多少对(x,y)满足x<y且第x个数和第y个数二进制下有k位不同。n<=200000,k<=14,ai<=10000
题解：搜索出所有k位的二进制数，最多3500左右，然后枚举ai判断。
复杂度2^14+10000*3500
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int a[];
int s[];
int num[];
ll ans=;
int n,k,cnt=; void dfs(int i,int j,int x)
{
if(i==){if(j==k)s[++cnt]=x;return;}
dfs(i+,j,x);
dfs(i+,j+,x|a[i]);
} int main()
{
a[]=;for(int i=;i<=;i++)a[i]=a[i-]<<;
n=read();k=read();
dfs(,,);
for(int i=;i<=n;i++){int x=read();num[x]++;}
for(int i=;i<=;i++)if(num[i])
for(int j=;j<=cnt;j++)
{int x=i^s[j];if(x>)continue;
if(k!=) ans+=1LL*num[i]*num[x];
else ans+=1LL*num[i]*(num[i]-);
}
cout<<(ans>>);
return ;
}