?
A. Playing with Paper
给一张矩形的纸，每次对折成一个正方形，然后对剩下的矩形重复操作，求最多可以获得多少个矩形
#include
#define ll long long using namespace std; ll a,b; int main() { scanf(%I64d%I64d,&a,&b); ll sum=0; ll r; while(b!=0){ sum+=(a/b); r=a%b; a=b; b=r; } printf(%I64d ,sum); return 0; }
B. Error Correct System
两个长度相同的字符串s，t，定义它们间的距离为同一位置如果两个字符不同就加1.
求通过一次交换s串中位置i，j的字符，使得距离最小
p[i][j]表示s串字符i对应t串字符j的下标，那么判断p[j][i]是否存在，或者p[j][k]
#include
const int MAXN=200010; using namespace std; int n; char s[MAXN],t[MAXN]; int p[26][26]; int main() { memset(p,0xff,sizeof(p)); int pa=-1,pb=-1; int sum=0; scanf(%d%s%s,&n,s,t); for(int i=0;i
C. Glass Carving
有一块长w，宽h的玻璃片，对它进行n次的操作，每次操作可以水平或者垂直切割它，输出每次切割后，所有切割所得的玻璃片中最大面积
用两个set分别保存水平和垂直方向切割的坐标，两个multiset保存水平和垂直方向切割所得的间距。
每次从set中二分查找比当前切割坐标x大的第一个r，比它小的最后一个l，这样切割就会产生新的间距r-x,x-l，而原来r-l的间距就被破坏了
#include
using namespace std; const int N = 200050; typedef long long LL; set
::iterator i, j; set
ve, ho; //记录所有边的位置 int wi[N], hi[N]; //记录存在的边长值 void cut(set
&s, int *a, int p) { s.insert(p), i = j = s.find(p); --i, ++j, --a[*j - *i]; //除掉被分开的长宽 ++a[p - *i], ++a[*j - p]; //新产生了两个长宽 } int main() { int w, n, h, p, mw, mh; char s[10]; while(~scanf(%d%d%d, &w, &h, &n)) { memset(wi, 0, sizeof(wi)), memset(hi, 0, sizeof(hi)); ve.clear(), ho.clear(); ve.insert(0), ho.insert(0); ve.insert(w), ho.insert(h); wi[w] = hi[h] = 1; mw = w , mh = h; while(n--) { scanf(%s%d, s, &p); if(s[0] == 'V') cut(ve, wi, p); else cut(ho, hi, p); while(!wi[mw]) --mw; while(!hi[mh]) --mh; printf(%lld , LL(mw)*LL(mh)); } } return 0; }
D. Clique Problem
题目是求最大团问题，是个NP问题
然后我们根据题目给的: |xi?-?xj|?≥?wi?+?wj.转化一下：
1. xi-xj≥wi+wj
<=>xi-wi>=xj+wj
2. -xi+xj≥wi+wj
<=>xi+wi<=xj-wj
如果把xi,wi看作一条线段的两个端点，那么不等式的意思就是线段i左端点比线段j右端点大，或者线段i的右端点比线段j的左端点小。
那么如果点i和点j有边连接的意思就是线段i和线段j不相交，最大团要使尽可能多的点之间都有边连接，就是求最多不相交的线段数。
那么就转化为 选择不相交区间问题，贪心
#include
const int MAXN=200050; using namespace std; struct node{ int l,r; bool operator<(const node&a)const{ return r
=tmp){ tmp=pos[i].r; ans++; } } printf(%d ,ans); return 0; }