[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;
}
}
IMUDGES OJ
IMUDGES
jasonczc
内蒙古大学OJ
文章评论