Codeforces Round #296 (Div. 2)——A.B.C.D

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;
}