今天和狄拉克去打了一下VKCUP2016的资格赛
发现俄文真是治愈人心……
所以这篇放一下题意吧
UPD Mar.15th 突然发现有英文题面了233
题意：有 $N$ 个人在投票，第 $i$ 个人投给选手$A_i$
问最后谁是票数最多的，票数一样的输出最先到达这个票数的
思路：模拟……
#include <cstdio>
#include <algorithm>
using namespace std;
int cnt[2000000],n,p,mx;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(++cnt[x]>mx) mx=cnt[x],p=x;}
printf("%d\n",p);
}
题意：你收到了 $N$ 条消息，第 $i$ 条消息是 $name_i$ 发来的
每次收到一条消息那个人的聊天框就会变到最上面，其他人相对顺序不变
一开始没有聊天框
要求输出最后聊天框从上到下的顺序
思路： 从后往前，如果没有出现过就直接输出。
用map维护。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
char S[15];
string s[200005];
map<string,int>a;
int n;
int main(){
n=IN();
Rep(i,1,n) scanf("%s",S),s[i]=string(S);
Drp(i,n,1) if (!a[s[i]]) puts(s[i].c_str()),a[s[i]]=1;
}
题意：有 $N$ 张票，每张票的编号是一个六位数，第 $i$ 张票的编号是 $A_i$
每张票的主人给出他记忆中的自己的票的编号，
然后售货员把与这个编号不同位数最少的那张票给他
问如果让每个主人都拿到自己的票，主人最多不能记错超过几位。
思路：$N^2$ 枚举两张票，然后取 $min\{ \frac{(Diff-1)}{2} \} $
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Rep(x, a, b) for(int x=a; x<=b; x++)
char s[1010][10];
int n,mn=6;
int main(){
scanf("%d",&n);
Rep(i,1,n) scanf("%s",s[i]+1);
Rep(i,1,n) Rep(j,i+1,n)
{
int tmp=0;
Rep(k,1,6) if(s[i][k]!=s[j][k]) tmp++;
mn=min(mn,tmp);
}
printf("%d\n",(mn-1)/2);
}
题意：有个跑道，长为 $m$ ,有 $n$ 个障碍，
障碍只能跳过去，你每次跳最多只能跳 $d$ 米，每次跳之前至少要助跑 $s$ 米
输出跑到终点的方案，跑不到的话输出 $IMPOSSIBLE$
思路：把中间不够助跑的两个障碍合成一个，
每次跳的时候贪心跳到障碍后面第一个位置就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=200005;
int cnt,n,m,s,d;
struct ZA{
int st,en;
bool operator <(const ZA&x)const{return st<x.st;}
}a[N],b[N];
int main(){
n=IN(),m=IN(),s=IN(),d=IN();
Rep(i,1,n) a[i].st=a[i].en=IN();
sort(a+1,a+n+1);
cnt=1;b[1]=a[1];
Rep(i,2,n) if (a[i].st-b[cnt].en-1<=s) b[cnt].en=a[i].en;
else b[++cnt]=a[i];
if (b[1].st<=s) return puts("IMPOSSIBLE"),0;
Rep(i,1,cnt) if (b[i].en-b[i].st+2>d) return puts("IMPOSSIBLE"),0;
int now=0,ns=0;
Rep(i,1,cnt){
ns=b[i].st-1-now;
printf("RUN %d\n",ns);
printf("JUMP %d\n",b[i].en-b[i].st+2);
now=b[i].en+1;
}
if (b[cnt].en!=m-1) printf("RUN %d\n",m-b[cnt].en-1);
}
下午去学了一下KD-Tree……
我是看jabby的博客学的→_→JABBY
比较快就打完了毕竟模板
然而打完时间一直爆炸
以为是人傻自带大常数
然后发现……第62行那边一直写的是x<now……
我以为这样可以……然而身败名裂
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=1000005,K=2;
int D,n,m,Cnt;
struct KDT{
int d[K],Mn[K],Mx[K];
KDT *l,*r;
bool operator <(const KDT&x)const{return d[D]==x.d[D]?d[D^1]<x.d[D^1]:d[D]<x.d[D];}
}a[N],*R,qry;
void Update(KDT *x,KDT *y){
if (!y) return;
Rep(i,0,K-1)
x->Mn[i]=min(y->Mn[i],x->Mn[i]),
x->Mx[i]=max(y->Mx[i],x->Mx[i]);
}
KDT *Build(int l,int r,int nd){
if (r<l) return 0;
D=nd;int mid=l+r>>1;
nth_element(a+l,a+mid+1,a+r+1);
Rep(i,0,K-1) a[mid].Mn[i]=a[mid].Mx[i]=a[mid].d[i];
a[mid].l=Build(l,mid-1,(nd+1)%K);
a[mid].r=Build(mid+1,r,(nd+1)%K);
Update(a+mid,a[mid].l),Update(a+mid,a[mid].r);
return a+mid;
}
void Insert(KDT *x){
D=0;
KDT *now=R;
while (1){
Update(now,x);
if (x->d[D]<=now->d[D]){if (!now->l){now->l=x;return;}now=now->l;}
else{if (!now->r){now->r=x;return;}now=now->r;}
D=D^1;
}
}
int GetDis(KDT *x){
if (!x) return oo;
int ret=0;
Rep(j,0,K-1){
if (qry.d[j]<x->Mn[j]) ret+=x->Mn[j]-qry.d[j];
if (qry.d[j]>x->Mx[j]) ret+=qry.d[j]-x->Mx[j];
}
return ret;
}
int Ans;
void Query(KDT *x){
int d0=0;
Rep(j,0,K-1) d0+=abs(qry.d[j]-x->d[j]);
Ans=min(Ans,d0);
int DL=GetDis(x->l),DR=GetDis(x->r);
if (DL<DR){
if (DL<Ans) Query(x->l);
if (DR<Ans) Query(x->r);
}
else{
if (DR<Ans) Query(x->r);
if (DL<Ans) Query(x->l);
}
}
int main(){
n=IN();m=IN();
Rep(i,1,n) Rep(j,0,K-1) a[i].d[j]=IN();
R=Build(1,n,0);
Cnt=n;
Rep(i,1,m){
int t=IN();
if (t==1){
++Cnt;
Rep(j,0,K-1) a[Cnt].d[j]=a[Cnt].Mn[j]=a[Cnt].Mx[j]=IN();
Insert(a+Cnt);
}
else{
Rep(j,0,K-1) qry.d[j]=IN();
Ans=1<<30;Query(R);
OUT(Ans),putchar('\n');
}
}
}
评论 (0)
