2015 北京现场赛4题
Xiongnu’s Land
题意与题解
这一题是第一题，算是个签到题吧，题目大意是一个(R,R)的地图上有若干个小矩形，让你画一条\(x=n\)的线，使得左边包含的矩形面积必须大于右边，且左边的土地面积要尽量大。数据中两两矩形不相交。
可以看到矩形两两不相交，我们直接从左到右扫描就行了，找到第一个面积合法的位置，然后尽量右移得到答案。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long
#define maxn 2000005
using namespace std;
struct Line
{
int l,v,x;
bool operator <(const Line &a) const
{
return x<a.x;
}
};
Line line[40005];
int K,R,n,L[maxn],T[maxn],W[maxn],H[maxn];
LL sum,area[maxn];
int main()
{
scanf("%d",&K);
while (K--)
{
int cnt=0;
memset(area,0,sizeof(area));
memset(line,0,sizeof(line));
memset(L,0,sizeof(L));
memset(T,0,sizeof(T));
memset(W,0,sizeof(W));
memset(H,0,sizeof(H)); sum=0;
scanf("%d%d",&R,&n);
for (int i=0;i<n;i++)
{
scanf("%d%d%d%d",&L[i],&T[i],&W[i],&H[i]);
sum+=1LL *W[i]*H[i];
line[cnt].l=H[i]; line[cnt].v=1; line[cnt].x=L[i];
cnt++;
line[cnt].l=H[i]; line[cnt].v=-1; line[cnt].x=L[i]+W[i];
cnt++;
R=max(R,L[i]+W[i]);
}
sort(line,line+cnt);
LL nowl=0,p=0;
for (int i=0;i<=R;i++)
{
if (i>0) area[i]=area[i-1]+nowl;
while (line[p].x==i && p<cnt)
{
nowl+=1LL*line[p].v*line[p].l;
p++;
}
}
int i=0;
for (i=0;i<=R;i++)
if (area[i]>=sum-area[i]) break;
while (area[i]==area[i+1] && i<=R) i++;
printf("%d\n",i);
}
return 0;
}Mysterious Antiques in Sackler Museum
题意与题解
这一题也很简单，给你4个小矩形，问你是否可以选取其中3个组成一个大矩形。对于这题我们枚举所有情况即可。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int T,w[7],h[7],sta[5];
bool vis[6];
bool check()
{
bool ans=0;
int a=sta[0],b=sta[1],c=sta[2];
ans=ans || ((w[a]==w[b] && w[b]==w[c]) || (w[a]==w[b] && w[b]==h[c])
|| (w[a]==h[b] && h[b]==w[c]) || (w[a]==h[b] && h[b]==h[c])
|| (h[a]==w[b] && w[b]==w[c]) || (h[a]==w[b] && w[b]==h[c])
|| (h[a]==h[b] && h[b]==w[c]) || (h[a]==h[b] && h[b]==h[c])) ;
if (ans) return 1;
ans=ans || ( (h[a]==w[b]+w[c] && h[b]==h[c]) || (w[a]==w[b]+w[c] && h[b]==h[c])
|| (h[a]==h[b]+w[c] && w[b]==h[c]) || (w[a]==h[b]+w[c] && w[b]==h[c])
|| (h[a]==w[b]+h[c] && h[b]==w[c]) || (w[a]==w[b]+h[c] && h[b]==w[c])
|| (h[a]==h[b]+h[c] && w[b]==w[c]) || (w[a]==h[b]+h[c] && w[b]==w[c])
);
return ans;
}
bool dfs(int d)
{
if (d==3)
return check();
for (int i=1;i<=4;i++)
{
if (!vis[i])
{
vis[i]=1; sta[d]=i;
if (dfs(d+1)) return 1;
vis[i]=0; sta[d]=0;
}
}
return 0;
}
int main()
{
scanf("%d",&T);
while (T--)
{
memset(w,0,sizeof(w));
memset(h,0,sizeof(h));
memset(vis,0,sizeof(vis));
memset(sta,0,sizeof(sta));
scanf("%d%d%d%d%d%d%d%d",&w[1],&h[1],&w[2],&h[2],&w[3],&h[3],&w[4],&h[4]);
if (w[1]>h[1]) swap(w[1],h[1]);
if (w[2]>h[2]) swap(w[2],h[2]);
if (w[3]>h[3]) swap(w[3],h[3]);
if (w[4]>h[4]) swap(w[4],h[4]);
if (dfs(0)) printf("Yes\n");
else printf("No\n");
}
return 0;
}Osu! Master
题意与题解
这一题题意大概是有一个游戏，分为三个element. C，B，和S，C和B有标号，S没有标号，顺序标号的C和B为一个组，S单独为一个组，问你在给定序列中总共有几组。
直接按照顺序模拟下来就行了。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,id;
char s[2];
int main()
{
while (scanf("%d",&n)!=EOF)
{
int ans=0,last=1;
while (n--)
{
scanf("%s",&s);
if (s[0]!='S') scanf("%d",&id);
if (s[0]=='S')
{
ans++; last=1;
}
else if (last+1==id) last++;
else
{
ans++; last=id;
}
}
printf("%d\n",ans);
}
return 0;
}Snake Carpet
题目大意
给你n条蛇，第i条蛇长度为i，现在要你设计一个矩形，把这n条蛇全部放在矩形上，要求蛇身不能相交。（每条蛇自己的身子也不能和自己相交）除此以外，奇数长度的蛇必须有正奇数个转点，偶数长度的蛇必须有正偶数个转点。要求输出这个矩形。
题解
题目虽然说如果有解才输出，但是稍微分析一下可以发现这个题其实我们是可以构造出来的。
首先可以根据蛇的数量确定矩形的长和宽。
对于奇数蛇，我们考虑矩形的右上角，依次放1，然后围绕着1填上3，再围绕着3填上5….这样一直下去，我们可以得到一个奇数的正方阵。
我们在总的矩形中把这个矩形剪掉，我们发现还剩下一个\(n(n+1)\)的矩形，这个矩形我们需要填上偶数，我们假设在第一行的1，2列填上2；对于4，我们在当前矩形的2下面填上4个4（2*2）；对于6，我们在当前矩形的右边填上6个6（2*3）….这样依次下去，我们可以完全得到偶数的构造方式。
我们得到奇数和偶数的构造方式以后，我们就可以输出了，不过偶数的阵有时候需要旋转一下，因为剪掉之后的矩形可能较长的边在左边，而我们构造的偶数阵是\(n(n+1)\)的。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct node
{
int x,y;
};
node ans[505][505];
int N,n,m;
void solve(int n,int m,int high)
{
int s=0,x=1,y=m,way;
//odd
for (int i=1;i<=N;i+=2)
{
int c=0; way=0;
x=1; y=m-s;
ans[i][c].x=x; ans[i][c].y=y;
c++;
while (c<i)
{
if (way==0)
{
ans[i][c].x=ans[i][c-1].x+1;
ans[i][c].y=ans[i][c-1].y;
c++;
}
else
{
ans[i][c].x=ans[i][c-1].x;
ans[i][c].y=ans[i][c-1].y+1;
c++;
}
if (c==s+1) way=1;
}
s++;
}
//even
if (N<=1) return ;
int cnt=0;
ans[2][0].x=1; ans[2][0].y=1;
ans[2][1].x=1; ans[2][1].y=2;
x=2; y=2; cnt++; way=1;
for (int i=4;i<=N;i+=2)
{
int c=0; cnt++;
if (way)
{
while (c<i/2)
{
ans[i][c].x=x; ans[i][c].y=y--;
c++;
}
x++; y=1;
while (c<i)
{
ans[i][c].x=x; ans[i][c].y=y++;
c++;
}
way=0;
}
else
{
while (c<i/2)
{
ans[i][c].x=x--; ans[i][c].y=y;
c++;
}
x=1; y++;
while (c<i)
{
ans[i][c].x=x++; ans[i][c].y=y;
c++;
}
way=1;
}
}
//change
int M1=0,M2=0,L;
if (way) L=x-1;
else L=y;
if (n<m-s) M1=1;
if (cnt%2!=0) M2=1;
if (M1!=M2)
{
for (int i=2;i<=N;i+=2)
for (int j=0;j<i;j++)
{
int t=ans[i][j].x;
ans[i][j].x=ans[i][j].y;
ans[i][j].y=L-t+1;
}
}
}
int main()
{
while (scanf("%d",&N)!=EOF)
{
memset(ans,0,sizeof(ans));
if (N&1)
{
n=(N+1)/2; m=N;
}
else
{
n=N/2; m=N+1;
}
solve(n,m,n*m);
printf("%d %d\n",n,m);
for (int i=1;i<=N;i++)
{
for (int j=0;j<i-1;j++) printf("%d %d ",ans[i][j].x,ans[i][j].y);
printf("%d %d\n",ans[i][i-1].x,ans[i][i-1].y);
}
}
return 0;
}