[toc]
这次校赛的题目总体上来说是比较简单的,出题中途怕大家做不出来,多次对题目降低了难度,其中最难的三题是改自省赛题,难度也就省赛简单点。不过本次题目没有水的数据,去年出题数据出太水了,结果好多人都是水过= =
A.qhq&php
这题题意很明显,就是查找最大的两个值。不过这题输入量不确定(且限制了内存),无法使用sort进行排序。此外还需要注意对字符串的处理。还有要注意收益k的取值范围,k是无法用int存下的。
标程(from jasonczc)
#include <string> #include <iostream> using namespace std; bool cmp(string a,string b){ if(a.length()!=b.length()) return a.length()>b.length(); return a>b; } int main(){ string ansa,ansb,ansa1,ansb1,a,b,tmp; while(getline(cin,tmp)){ long long int start=tmp.length()-1,length=0; while(tmp[start]!=' ') start--,length++; a = tmp.substr(0,start); b = tmp.substr(start+1,length); if(cmp(b,ansb1)){ if(cmp(b,ansb)){ ansb1=ansb; ansa1=ansa; ansb = b; ansa = a; }else{ ansb1 = b; ansa1 = a; } } } cout << ansa << endl << ansa1; }
B.可怜的qhq
这题改自前年的省赛题。这题在思考上有些难度,但是出题后降低了难度,直接在提示中告知了本题的做法。首先正反面肯定要先计算一次,然后正反面整理完后,就相当求逆序对数了。求逆序对数可以使用归并,也可以使用树状数组。
标程
#include<cstdio> #include<string.h> #include<iostream> using namespace std; int a[100000+5],idx; int bit[100000+5]; int sum(int i) { int s=0; while(i>0) { s+=bit[i]; i-=i&-i; } return s; } void add(int i,int x) { while(i<=idx) { bit[i]+=x; i+=i&-i; } } int main() { int n; while(scanf("%d",&n)==1) { int ans1=0,t; memset(bit,0,sizeof(bit)); idx=0; for(int i=0;i<n;++i) { scanf("%d",&t); if(!(i&1)) { if(!(t&1))ans1++; a[idx++]=(t+1)/2; } } long long ans2=0; for(int i=0;i<idx;i++) { ans2+=i-sum(a[i]); add(a[i],1); } printf("%lld\n",ans1+ans2); } }
C.qhq的服务器
改自今年省赛热身赛的题目,二分即可,注意本题的数据范围。
标程
#include <bits/stdc++.h> using namespace std; long long a[100010],tmp; int t,n,m; int main(){ scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); for(int i = 1;i<=n;i++){ scanf("%lld",a+i); a[i]+=a[i-1]; } for(int i = 1;i<=m;i++){ scanf("%lld",&tmp); long long p = lower_bound(a+1,a+1+n,tmp)-(a+1); printf("%lld %lld\n",p+1,tmp-a[p]); } } }
D.qhq的神奇表
改自某年的noip题,推出公式即可
标程
#include<cstdio> #include<math.h> int main() { int n; while(scanf("%d",&n)==1) { int a=(-1.0+sqrt(1+8*(n-1)))/2+2; int b=(a-2)*(1+a-2)/2; if(a&1) { printf("%d/%d\n",n-b,a-(n-b)); } else { printf("%d/%d\n",a-(n-b),n-b); } } }
E.新的主角~皮神,登场!
Hello world,直接输出即可
标程
#include<cstdio> int main() { printf(" _0& \n 000 \n 0000 \n j0000f \n ]00000& \n 000000& \n j000000# \n 00000000 \n j00000M^] \n 0000~ ] \n ]00M ] \n #0& ] \n 0' l \n ]' ! \n l f \n I \n A \n H ] \n - [ __,,aa-----* ..__ \n c ' __,,____ _,.**~^ \"\"-w_ \n U ,-:~ `7*^ 0Mg, \n 6 ? ,\" ,000000gg \n ! L/` _g0000000000g, \n | _/` _p000000000000000r \n ] ` Y+*:,__ gM00000000000000MM^ \n 1 ``~~\"\"~~~~~~~~~~`` \n f ' \n l[ \n _gg_ f \n i pF`M0& 1 \n ! 0g _00& ] q /f \n L __ 000000# t ,/^ ^ \"\" \n L g0M~Qp ^00000' ] ,*^ ` _, ,\n ! q00 ]0 ~M~ _1 x^ \", _,a*\"~ _ \n l 400&g00 _g jD00_x^ _/' _,a=~` } \n ] \"00000# ` ]0#MMI ' ,a+~` \n ^M00M _____ ,' 0NQ#gH ) _,-\"` 1 \n _p0N0M0000# _0000g# _,+\" \n _ -..pg##M000M#000 \"M000gV f ,*\" ! \n ]M#g M000N0MM0NR00 0000K6 J _.*` w \n ^\\.a---*+*400#& 400NN0QK0### M000# y _/~ I \n V`` ]KAQ0L #M0N@^`#IFM `\"4 ,/~ \n,\" ##Q0d #NN:{E-T-j y~ ' _/' ? \n`1 \"#M04 Q: m S,n! , ' \n7 &0I Y@^:G%,\" ) y' J \n \", \\ , w7 _/ p' ] ' \n w*( *, 'q_W ^ v ] j \n *, ~m_ / | f \n \\_ +v_ $^ ` I ___,x.m/* \n \\, \"* \\ P __,/***\"\"~~` \n *q t 6 _,m+-~~^` \n ~\\, \" W ! \n ~*._ ___ l 6 \n ~**Q_ ,*` `~< Y \n _ / >. ] ] 4 \n 6 pwT>f 1 a,,,,J l \n f i] Y \\ ] ] I \n ~ q\\ ( `. ]_ \n c\\ \\ \\ - f l# Y--**vL,_ \n ] \\ ' $g_]0NXgI \n ]`, #M000##Mf \n n \" ^, BM0N00001 \n 6 1 \"q / _0N0N0&0MI \n t \", \\ l Q0# ~M0M01 \n f ^} >, ~W _N0 ` \n n \"c *, l y&Mf \n \"*' 7~` \n ] _+` \n | ,+~ \n ] _)\" \n ] W~ \n _ )^ \n ] p' \n \\ / \n \\ p/ \n ^v ,~ \n R*g_____.*\" \n 5\\ `j \n x r/! \n ] / \\\\ \n ] > J \n ]Q ^' \n ]] \\7 \n j \"_ \n 0 ^ \n V^ "); }
F.逃げる!电気石の洞穴
改自今年省赛热身赛,最最基础的搜索入门题。注意审题,终点可能有多个。
标程
#include<cstdio> #include<queue> #include<cstring> using namespace std; char maze[205][205]; int flag[205][205]; int d[4][2]={0,1,1,0,0,-1,-1,0}; struct point{ int x,y,t; point(int _x,int _y,int _t){x=_x;y=_y;t=_t;} }; int main() { int t,n,m,sx,sy; scanf("%d",&t); while(t--) { memset(flag,0,sizeof(flag)); scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { getchar(); for(int j=0;j<m;j++) { scanf("%c",&maze[i][j]); if(maze[i][j]=='R') { sx=i; sy=j; } } } queue<point> q; point s(sx,sy,0); q.push(s); flag[sx][sy]=1; int f=1; while(!q.empty()) { point p=q.front(); q.pop(); if(maze[p.x][p.y]=='F') { printf("%d\n",p.t); f=0; break; } for(int i=0;i<4;i++) { int nx=p.x+d[i][0]; int ny=p.y+d[i][1]; if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]!='#'&&!flag[nx][ny]) { flag[nx][ny]=1; point s(nx,ny,p.t+1); q.push(s); } } } if(f)printf("Poor Pikachu.\n"); } }
G.皮卡丘的精灵图鉴
并查集。注意对字符串的处理。
标程(from jasonczc)
#include <iostream> #include <string> #include <unordered_map> using namespace std; unordered_map<string,string> m; string& find(string &t){ if(m.find(t)==m.end()){ return t; }else{ string st = m[t]; if(st==t) return t; else return m[t]=find(st); } } void merge(string &a,string &b){ string fa=find(a),fb=find(b); if(fa!=fb) m[fa]=fb; } int main(){ int k;cin >> k; while(k--){ int a,b; cin >> a >> b; string sa,sb; while(a>0){ cin >> sa >> sb; merge(sa,sb); a--; } while(b>0){ cin >> sa >> sb; cout << ((find(sa)==find(sb))?"Y":"N")<< endl; b--; } m.clear(); } }
H.自闭了
博弈水题,只要n>2,都是pkq赢
标程
#include<iostream> using namespace std; int main() { int n; while(cin>>n&&n) { if(n<=2)cout<<"qhq"<<endl; else cout<<"pkq"<<endl; } }
文章评论