3
14
2016
0

Diary of March 14th

今天和狄拉克去打了一下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');
		}
	}
}

 

Category: Diary | Tags: kd-tree 模拟 排序 贪心 map | Read Count: 217

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com