2015 Syrian Private Universities Collegiate Programming Contest 题解
题目在这里>_<
发现这场比赛在网上没有完整的题解，甚至连题目代码都没人贴出来（大概是因为题目太水了吧。。。）。所以宝宝就来写个题解，也就当作成长记录了233333
A. Window
题意很简单，给出n组x，y，求x*y的值
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int n;
long long x,y;
scanf("%d",&n);
while(n--)
{
scanf("%I64d%I64d",&x,&y);
printf("%I64d\n",x*y);
}
return 0;
}
B. Paper Game
两个人撕纸片玩，会发现其实能够撕的次数就是x*y，所以就很简单啦^_^
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int t;
int x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&x,&y);
if((x*y)&1)
printf("Hussain\n");
else
printf("Hasan\n");
}
return 0;
}
C. Rectangles
计数，由于数据范围比较小，O(n)就能过了，根本不需要树状数组线段树神马的。把题目改为输入i,j,k,s再把数据范围改大一点，就需要二维树状数组了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax=105;
int high[Nmax];
int t,n,z,x,y,ans;
void init()
{
ans=0;
for(int i=0;i<Nmax;i++)
high[i]=0;
}
int main()
{
//freopen("c.in","r",stdin);
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d",&z,&x,&y);
for(int i=z+1;i<=x;i++)
high[i]=max(high[i],y);
}
for(int i=1;i<Nmax;i++)
ans+=high[i];
printf("%d\n",ans);
}
return 0;
}
D. Sequences
求元素间恰好只差1的最长上升子序列，英语渣表示读题的时候没读懂一定要只差1，然后各种看不懂样例2333333 我们知道条件限制越多就越好写，所以必须只差1的话，用dp[i]记录到值为i的元素的最长上升子序列，因此dp[i]=max(dp[i],dp[i-1]+1)，O(n)水过。
#include<cstdio>
#include<algorithm>
using namespace std;
const int Nmax=20005;
int dp[Nmax];
int t,n,x,ans;
int main()
{
//freopen("d.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans=0;
for(int i=0;i<Nmax;i++)
dp[i]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
dp[x]=max(dp[x],dp[x-1]+1);
ans=max(ans,dp[x]);
}
printf("%d\n",ans);
}
return 0;
}
E. Napoléon
问在8*8的棋盘上，一个只能斜着走的棋子从某点到另一点的最小步数。
只能斜着走的话，显然(x+y)的奇偶性相同才能互相到达。虽然是斜着走，但是每次都能向目标方向靠近一个单位，所以最小步数就是max(|x1-x2|,|y1-y2|) 。
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int Nmax=25;
int dis[Nmax][Nmax];
int n,t;
int xs,ys,xe,ye;
int get_num(int x,int y)
{
return (x-1)*n+y;
}
int abs(int x)
{
if(x<0)
return -x;
return x;
}
int main()
{
//freopen("e.in","r",stdin);
scanf("%d%d",&t,&n);
while(t--)
{
scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
xs++,ys++,xe++,ye++;
// printf("%d %d %d %d\n",xs,ys,xe,ye);
// printf("%d %d\n",(xs+ys)&1,(xe+ye)&1);
if( ((xs+ys)&1)!=((xe+ye)&1) )
printf("can't reach!\n");
else
printf("%d\n",max( abs(xs-xe),abs(ys-ye) ));
}
return 0;
}
F. The Best Strategy
又死在了英语上ψ(╰_╯) 做了这题我才知道罚时是怎么算的。。。然而题目里没告诉罚时怎么算，所以又是看不懂样例系列。原来总罚时就是每道题在比赛中的完成时间之和。所以排个序模拟一下就好了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax=305;
int num[Nmax];
int sum,ans,number,now;
void init()
{
sum=ans=number=now=0;
}
int main()
{
int t,n;
//freopen("f.in","r",stdin);
scanf("%d",&t);
for(int k=1;k<=t;k++)
{
scanf("%d",&n);
init();
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
sort(num+1,num+n+1);
for(int i=1;i<=n;i++)
{
if(now+num[i]<=300)
{
now=now+num[i];
sum+=now;
number++;
}
else
break;
}
printf("Case %d: %d %d\n",k,number,sum);
}
}
G. Cutie Pie
找到一堆字符里面的“pie”，思路很简单，暴力BFS就好啦~
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int Nmax=25;
char map[Nmax][Nmax];
int t,n,m,nowx,nowy,kkk,nowxx,nowyy;
int dx[]={-1,-1,-1, 0,0, 1,1,1};
int dy[]={-1, 0, 1,-1,1,-1,0,1};
struct Node
{
int x;
int y;
}p;
queue<Node> q;
int get_num(int x,int y)
{
return (x-1)*m+y;
}
void init()
{
while(!q.empty())
q.pop();
}
int main()
{
//freopen("g.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
getchar();
map[i][j]=getchar();
if(map[i][j]=='p')
q.push((Node){i,j});
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=m;j++)
// printf("%c ",map[i][j]);
// printf("\n");
// }
// while(!q.empty())
// {
// p=q.front();
// q.pop();
// printf("%d %d\n",p.x,p.y);
// }
int ans=0;
while(!q.empty())
{
if(ans)
break;
p=q.front();
q.pop();
for(int i=0;i<8;i++)
{
if(ans)
break;
nowx=p.x+dx[i],nowy=p.y+dy[i];
kkk=get_num(nowx,nowy);
if(kkk>=1 && kkk<=n*m && map[nowx][nowy]=='i')
{
for(int j=0;j<8;j++)
{
nowxx=nowx+dx[j],nowyy=nowy+dy[j];
kkk=get_num(nowxx,nowyy);
if(kkk>=1 && kkk<=n*m && map[nowxx][nowyy]=='e')
{
ans=1;
break;
}
}
}
}
}
if(ans)
printf("Cutie Pie!\n");
else
printf("Sorry Man\n");
}
return 0;
}
H. Weekend
问一个人从起点到终点接上所有朋友的最短时间。先把每两个点间的最短距离求出来，再对所有的朋友点跑一个记忆化搜索。因为朋友数很少，状态压缩一下记录所有的状态，再用dp[i][j]记录到点i时状态j的最短时间，就搞定啦ヾ(´▽‘)ﾉ 然而我居然漏写了一个等号，然后一直TLE 23333
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax=1005;
const int INF=1e9;
int ans,ans_min;
int dis[Nmax][Nmax];
int map[Nmax][Nmax];
int x,y,w,n,m,f;
int num[Nmax];
int book[Nmax],step;
void init()
{
ans=0;
step=0;
ans_min=INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=INF;
for(int i=1;i<=n;i++)
dis[i][i]=num[i]=book[i]=0;
}
void dfs(int now)
{
if(now==f+2)
{
if(step==f+2)
ans_min=min(ans_min,ans);
return;
}
for(int i=1;i<=f+2;i++)
{
if(dis[num[now]][num[i]]<INF)
{
if(!book[i])
{
ans+=dis[num[now]][num[i]];
step++;
book[i]=1;
dfs(i);
ans-=dis[num[now]][num[i]];
step--,book[i]=0;
}
else
{
ans+=dis[num[now]][num[i]];
dfs(i);
ans-=dis[num[now]][num[i]];
}
}
}
}
int main()
{
freopen("h.in","r",stdin);
int t;
scanf("%d",&t);
for(int k=1;k<=t;k++)
{
scanf("%d%d%d",&n,&m,&f);
init();
printf("Case %d: \n",k);
while(m--)
{
scanf("%d%d%d",&x,&y,&w);
dis[x][y]=dis[y][x]=map[x][y]=map[y][x]=w;
}
for(int tmp=1;tmp<=n;tmp++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(dis[i][tmp]+dis[tmp][j]<dis[i][j])
dis[i][j]=dis[i][tmp]+dis[tmp][j];
}
}
}
num[1]=1;
book[1]=1,step++;
for(int i=2;i<=f+1;i++)
scanf("%d",&num[i]);
num[f+2]=n;
dfs(1);
printf("%d\n",ans_min);
}
return 0;
}
I. Playing With Strings
模拟模拟！
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
const int Nmax=1005;
char ans[Nmax];
int n,t,now;
int num[26];
char s[Nmax];
char c;
void init()
{
now=1;
for(int i=0;i<=n+1;i++)
ans[i]='\0';
for(int i=0;i<26;i++)
num[i]=0;
for(int i=0;i<n;i++)
{
c=s[i];
num[c-'a']++;
}
int ct=0;
for(int i=0;i<26;i++)
{
if(num[i]&1)
ct++;
}
if(ct>1)
{
printf("impossible\n");
return;
}
for(int i=0;i<26;i++)
{
int kkkk=1;
kkkk=0;
if(num[i]&1)
ans[(n>>1)+1]=i+'a',num[i]--;
while( (num[i]-2)>=0 )
{
ans[now]=ans[n+1-now]=i+'a';
num[i]-=2;
now++;
}
}
puts(ans+1);
}
int main()
{
//freopen("i.in","r",stdin);
scanf("%d",&t);
getchar();
while(t--)
{
scanf("%s",s);
n=strlen(s);
init();
}
return 0;
}
J. Good Coins
求gcd(i,j)是否为1。所以标程当然是gcd了，然而数据太水，所以用超慢超蠢的无限减法写法过了23333
#include <cstdio>
#include <algorithm>
using namespace std;
int x,y;
int t;
int make(int a,int b)
{
if(a<0 || b<0)
return 0;
if(a==1 || b==1)
return 1;
if(a<b)
return make(b,a);
if(a==b)
return 0;
return make(a-b,b);
}
int main()
{
//freopen("j.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&x,&y);
if(make(x,y))
printf("GOOD\n");
else
printf("NOT GOOD\n");
}
return 0;
}
K. Clash Of Snakes
求在nm的格子上，1s和1*k的长条互不重叠的摆法个数。原问题是有方向的，但是没关系，我们只要在没方向的方案数上乘4就是答案了。
用容斥原理，先求出来单独摆s和摆k的个数，再求出重叠的个数，一减就是答案了。然而要注意的是，模运算中，模完再做减法可能会出负数，所以最后要特判一下（就是因为这个负数，一直wa在第二个点，呜呜呜）。
由于本人比较懒，所以写了ll类型用来求模，虽然在相同写法上速度可能会慢点，但是容易检查而且不易写错，还是值得的。最终还是只有15ms就通过啦ヾ(o◕∀◕)ﾉヾ
#include <cstdio>
#include <algorithm>
using namespace std;
const int Mod=1000000007;
struct ll
{
long long x;
ll() {x=0;}
ll(long long tttt) {x=tttt;}
ll operator + (ll b)
{
ll c;
c.x=(x+b.x)%Mod;
return c;
}
ll operator * (ll b)
{
ll c;
c.x=(x*b.x)%Mod;
return c;
}
ll operator -(ll b)
{
ll c;
c.x=(x-b.x)%Mod;
return c;
}
};
ll get(ll n,ll m,ll k)
{
ll get_value(0);
if(k.x<=m.x && k.x<=n.x)
return (m-k+1)*n + (n-k+1)*m;
if(k.x>m.x && k.x<=n.x)
return (n-k+1)*m;
if(k.x>n.x && k.x<=m.x)
return (m-k+1)*n;
return get_value;
}
ll max(ll a,ll b)
{
if(a.x>=b.x)
return a;
else
return b;
}
ll min(ll a,ll b)
{
if(a.x<=b.x)
return a;
else
return b;
}
int main()
{
//freopen("k.in","r",stdin);
int t;
ll two(2),four(4),one(1),eight(8);
scanf("%d",&t);
long long tmpn,tmpm,tmps,tmpk;
for(int i=1;i<=t;i++)
{
scanf("%I64d%I64d%I64d%I64d",&tmpn,&tmpm,&tmps,&tmpk);
ll n(tmpn),m(tmpm),s(tmps),k(tmpk);
ll l=max(k,s);
ll r=min(k,s);
ll ans=(two*m*n-(m+n)*(k-one))*(two*m*n-(m+n)*(s-one));
ll a=min(m,k+s-one);
ll b=min(n,k+s-one);
ans=ans-k*s*( (n-s+one)*(m-k+one)+(n-k+one)*(m-s+one) );
ans=ans-(m-l+one)*n*(l-r+one)-(n-l+one)*m*(l-r+one);
ans=ans-n*(a-l)*( two*(m+one)-(a+l+one) );
ans=ans-m*(b-l)*( two*(n+one)-(b+l+one) );
ans=ans*four;
if(ans.x<0)
ans.x+=Mod;
printf("Case %d: %I64d\n",i,ans.x);
}
return 0;
}
