首页 > 代码库 > Test on 09/10/2016
Test on 09/10/2016
1．勇士闯塔
(tower.pas/c/cpp)
【问题描述】
在遥远的东方，有一座膜塔，膜王抓走了公主，并将其囚禁在膜塔的21层，勇士需要闯塔，解救公主。
现在勇士的前方有n个膜怪，每一个膜怪有一个属性值ai，属性值不同的膜怪视为不同种类的膜怪，现在勇士想知道在第qi~qj个膜怪中有多少种不同的膜怪，请你帮忙解决。
【输入格式】
第1行：2个整数n，q，分别表示膜怪数量以及询问数。
第2行：n个整数，表示每个膜怪的属性值。
第3~q+2行：每行2个整数qi，qj.
【输出格式】
共q行，每行一个整数，表示答案。
【输入输出样例1】
tower.in | tower.out |
6 3 1 2 3 4 3 5 1 2 3 5 2 6 | 2 2 4 |
【输入输出样例2】
tower.in | tower.out |
10 5 1 3 5 5 3 3 2 5 4 3 3 3 6 7 5 10 3 6 2 6 | 1 2 4 2 2 |
【数据范围】
对于70%的数据，n ≤ 100，q ≤ 1000；
对于100%的数据，n ≤ 3000，q ≤ 200000，1 ≤ a[i] ≤1000；
数据保证qi ≤ qj。
虽然自己没写但是应该是会的，我觉得应该是用一个数组记录下来从1到i所有的膜怪种类数，然后读入询问，s【qj】-s【qi-1】；
然而题解写的吓到我了。
70分的话O（n^2）的简单算法，在回答询问时，调用上一个询问的答案，例如，有一段区间，1、3、1、1、3、2。上一个询问是1~4，答案是ans，现在有一个询问3~5，那么我们只需要计算1、2、5位置的数对答案的贡献，然后处理一下就行了。
100分需要优化到O（nlogn），也就是传说中的莫队算法。我们可以先将数列分成根号n块，如果一个询问的左端点落在第i块，那么这个询问属于第i块，
那么我们就可以按块处理询问，每个块内将询问按右端点排序，然后处理即可。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int main() 5 { 6 freopen("tower.in","r",stdin); 7 freopen("tower.out","w",stdout); 8 int n,q,a[3001]; 9 cin>>n>>q;10 for(int i=1;i<=n;i++)11 cin>>a[i];12 for(int i=1;i<=q;i++)13 {14 int x,y,s=0,b[1001]={};15 cin>>x>>y;16 for(int j=x;j<=y;j++)17 {18 if(b[a[j]]==0)19 {b[a[j]]=1;s++;}20 }21 cout<<s<<endl;22 }23 return 0;24 }
2．勇士的背包
(bag.pas/c/cpp)
【问题描述】
经过千辛万苦，勇士终于来到了第15层，这是一个特殊的地方——装备库。
这里一共有N件装备，每一个装备有一个价值Pi和重量Wi，当时由于这些装备没有被长者开光，有些装备不能放在一起，否则会引起共鸣，释放洪荒之力，世界毁灭。并且这种共鸣具有专递性，例如，A不能和B放在一起，B不能和C放在一起，则A也不能和C放在一起。
勇士想知道在他的能力范围内，最多能获得多少价值的装备。
【输入格式】
第1行：3个整数N、M、K，N表示装备件数，M表示勇者的最大负重，K表示有K个(断句)装备不能放在一起的关系。
接下来N行：每行2个整数，Pi、Wi，分别表示每件装备的价值和重量。
接下来K行：每行2个整数A、B，表示第A件装备不能和第B件装备放在一起。
【输出格式】
一个整数，表示所能获得的最大价值。
【输入输出样例】
bag.in | bag.out |
3 10 1100 1200 510 51 2 | 210 |
【数据范围】
对于40%的数据，K=0
对于100%的数据，0≤N,M,K≤1000，0≤Pi≤10000,1 ≤Wi≤ 10,均为整数，A、B不相等
第一眼看着咦，这不是贪心么，嗯是简单的dp，然而dp还没开始搞，这意味着40分我都拿不到手。嗯回来写01背包。
100分的话需要用并查集维护装备间的关系，把不能放在一起的装备放在一个集合中，这样就转化为了集合背包问题。
并查集是什么QAQ 并查集是有关树的，然而看到树就好高端的样子。
不会滚粗。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<algorithm> 7 using namespace std; 8 int n,w,k,len,v[1010],c[1010],f[1010],F[1010],s[1010],a[1010][1010]; 9 inline int read()10 {11 int x=0,f=1; char ch=getchar();12 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();}13 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();}14 return x*f;15 }16 int find(int x)17 {18 return f[x]==x?x:f[x]=find(f[x]);19 }20 void work(int x)21 {22 for(int i=1;i<=len;i++)23 if(find(x)==a[i][0]) {s[i]++; a[i][s[i]]=x; return;}24 len++;25 s[len]=1;26 a[len][s[len]]=x;27 a[len][0]=find(x);28 }29 int main()30 {31 freopen("bag.in","r",stdin);32 freopen("bag.out","w",stdout);33 n=read(); w=read(); k=read();34 for(int i=1;i<=n;i++)35 f[i]=i;36 for(int i=1;i<=n;i++)37 v[i]=read(),c[i]=read();38 for(int i=1;i<=k;i++)39 {40 int x=read(),y=read();41 x=find(x); y=find(y);42 if(x!=y) f[x]=y;43 }44 for(int i=1;i<=n;i++)45 work(i);46 for(int i=1;i<=len;i++)47 for(int j=w;j>=0;j--)48 for(int k=1;k<=s[i];k++)49 if(j-c[a[i][k]]>=0) F[j]=max(F[j],F[j-c[a[i][k]]]+v[a[i][k]]);50 printf("%d",F[w]);51 return 0;52 }
3．勇士斗膜王
(moking.pas/c/cpp)
【问题描述】
“你还是来了！”
“是的，我来了！”
“膜膜膜……”
“不愧是膜王……”
在膜塔的巅峰——21层上，一场惊世对决开始了。
勇士亮出了他的N件法宝，要启动全部的法宝才能击败膜王，但是，启动第i件法宝需要消耗一个法力值不低于Ai且美观程度不低于Bi的魔石，现在勇士有M块魔石，第i块魔石的法力值为Ci，美观程度为Di，勇士想知道为了打败膜王，需要消耗的魔石的法力值的总和最小为多少。
【输入格式】
第1行：2个整数N、M。
接下来N行：每行2个整数Ai，Bi。
接下来M行：每行2个整数Ci，Di。
【输出格式】
一个整数，表示需要消耗的魔石的法力值的总和的最小值。
若无法打败膜王，输出“Failed”。
【输入输出样例1】
moking.in | moking.out |
2 3 2 7 5 2 4 1 8 8 7 1 | Failed |
【输入输出样例2】
moking.in | moking.out |
3 4 1 3 4 7 6 6 5 5 6 4 7 9 9 10 | 21 |
【数据范围】
对于30%的数据，1≤N≤5000，1≤M≤5000
对于100%的数据，1≤N≤100000，0≤M≤100000
这该说点什么，最大的暴力就是直接输出Failed ，然而我和我的小伙伴都以为至少30+，然而好像只有 FIVE
//三十分的数据根据美观程度sort，然后找符合的瞎搞搞就好了
100算法：我们先将魔石和法宝的美观程度（第二关键字）按从大到小排序，然后对于每件法宝，我们枚举魔石的美观程度，如果合法，把魔石的价钱插入到平衡树中，然后在平衡树中找法宝要求的法力值的后继，如果找不到，就输出Failed，找完之后把该价钱从平衡树中删除，顺便记录一下答案，输出即可。
最后注意使用long long，否则会爆掉。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 long long ans;10 int n,m,len,root,temp;11 struct node1{int l,r,v,w,fix;}tr[100100];12 struct node2{int x,y; bool operator<(const node2 a)const{return y>a.y;}}g[100100],c[100100];13 void lturn(int &p) {int c=tr[p].r; tr[p].r=tr[c].l; tr[c].l=p; p=c;}14 void rturn(int &p) {int c=tr[p].l; tr[p].l=tr[c].r; tr[c].r=p; p=c;}15 inline int read()16 {17 int x=0,f=1; char ch=getchar();18 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();}19 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();}20 return x*f;21 }22 void insert(int &p,int v)23 {24 if(!p) {p=++len; tr[p].v=v; tr[p].w=1; tr[p].fix=rand(); return;}25 if(v==tr[p].v) tr[p].w++;26 else if(v<tr[p].v) {insert(tr[p].l,v); if(tr[p].fix>tr[tr[p].l].fix) rturn(p);}27 else {insert(tr[p].r,v); if(tr[p].fix>tr[tr[p].r].fix) lturn(p);} 28 }29 void del(int &p,int v)30 {31 if(tr[p].v==v)32 {33 if(tr[p].w>1) tr[p].w--;34 else if(tr[p].l*tr[p].r==0) p=tr[p].r+tr[p].l;35 else if(tr[tr[p].l].fix<tr[tr[p].r].fix) {rturn(p); del(p,v);}36 else {lturn(p); del(p,v);}37 }38 else if(v<tr[p].v) del(tr[p].l,v);39 else del(tr[p].r,v);40 }41 void find(int p,int v)42 {43 if(!p) return;44 if(tr[p].v>=v) {temp=tr[p].v; find(tr[p].l,v);}45 else find(tr[p].r,v);46 }47 int main()48 {49 freopen("moking.in","r",stdin);50 freopen("moking.out","w",stdout);51 n=read(); m=read();52 for(int i=1;i<=n;i++) c[i].x=read(),c[i].y=read();53 for(int i=1;i<=m;i++) g[i].x=read(),g[i].y=read();54 sort(c+1,c+n+1); sort(g+1,g+m+1);55 int j=1;56 for(int i=1;i<=n;i++)57 {58 temp=-1;59 while(g[j].y>=c[i].y&&j<=m) {insert(root,g[j].x); j++;}60 find(root,c[i].x);61 if(temp==-1) {printf("Failed\n"); return 0;}62 ans+=temp; del(root,temp);63 }64 printf("%I64d\n",ans);65 return 0;66 }
最大估计 145.
立flag
1.哈希表
2.并查集
3.01背包
Test on 09/10/2016