130712周赛（CF）

这次练习从第一题开始注定水了，1A的题目wa了3次，第三题走进了错误的思想，wa到死....其他三个题目看都没看...........赛后慢慢搞。

A. Free Cash

巨水的一题，直接找出每个时间点出现次数最多那个值。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 1050
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

int vis[30][60];

int main()
{
    int t,a,b;
    cin >> t;
    int max = 0;
    for(int i=0; i<t; i++)
    {
        cin >> a >> b;
        vis[a][b]++;
    }
    for(int i=0; i<=23; i++)
    {
        for(int j=0; j<=59; j++)
        {
            if(max < vis[i][j])
                max = vis[i][j];
        }
    }
    cout << max << endl;
    return 0;
}

B. Young Table

赛后看的，special judge的话，只要交换次数不大于点的个数都行，于是有很多想法，排好序来搞，或者让当前点与它的所有右，下方点的最小值比较，大则交换。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 1050
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

int c[MAX];
int map[MAX][MAX];

struct node
{
    int x1,y1,x2,y2;
} step[MAX];
int n;

int main()
{
    int i,j,k,tx,ty;
    while(cin >> n)
    {

        for(i=1; i<=n; i++)
            scanf("%d",&c[i]);
        int cnt=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=c[i]; j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=c[i]; j++)
            {
                int t = map[i][j];
                for(k=i; k<=n; k++)
                for(int l=j; l<=c[k]; l++)
                {
                    if(t > map[k][l])
                    {
                        t = map[k][l];
                        tx = k;
                        ty = l;
                    }
                }
                if(map[i][j] > t)
                {
                    swap(map[i][j],map[tx][ty]);
                    step[cnt].x1 = i;
                    step[cnt].x2 = j;
                    step[cnt].y1 = tx;
                    step[cnt].y2 = ty;
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
        for(i=0; i<cnt; i++)
            cout << step[i].x1 << ' ' << step[i].x2 << ' ' << step[i].y1 << ' ' << step[i].y2 << endl;
    }
    return 0;
}

C. Primes on Interval

wa到死....第一感觉没有往二分方向思考（还是缺少二分的感觉），个人想法是：把所有的素数列出来，如果要满足L长度范围内至少有k个素数，那么保证L长度内刚好有K个素数情况下，L能取最短。然后枚举间隔k个素数之间的长度差的最大值就是L了，但是这种思考漏洞太多，最后只能二分解决。二分L长度，找到符合要求的mid值的最小值。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 1000050
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

int prime[MAX];
int cnt[MAX];
void isprime()
{
    prime[0] = 1;
    prime[1] = 1;
    for(int i=2; i<=1000000; i++)
    {
        if(prime[i] == 0)
            for(int j=2*i; j<=1000000; j+=i)
                prime[j] = 1;
    }
}

int main()
{
    int a,b,k,minn = 1000000;
    cin >> a >> b >> k;
    isprime();
    for(int i=a; i<=b ; i++)
    {
        if(prime[i] == 0)
            cnt[i] = 1;
        cnt[i] += cnt[i-1];
    }
    int l = 1, r = b-a+1,mid;
    int ok2 = 0;
    while(l <= r)
    {
        mid = (l+r) /2;
        int ok = 0;
        for(int i=a; i<=b+1-mid; i++)
        {
            if(cnt[i-1+mid] - cnt[i-1] < k)
            {
                l = mid + 1;
                ok = 1;
                break;
            }
        }
        if(ok == 0)
        {
            ok2 = 1;
            minn = min(minn,mid);
            r = mid - 1;
        }
    }
    if(ok2)
        cout << minn << endl;
    else
        cout <<  -1 << endl;
    return 0;
}

D.T-decomposition

这题题目意思真心没看懂

题意（转自魏神）：

给了一颗树s，然后让你构造一个树叫t，
t这颗树比较特别，就是这颗树上的结点都是由树s上的若干结点构成的集合。 并且t树上所有结点的并集是s树的结点的全集
并且，如果s上有边（a,b）那么t树上必须有某个结点，包含a和b这两个点。
最后一条，如果t树上有两个结点x,y，若x中包含了s树中的结点a，且y中包含了s树中的结点a，那么t树中，x到y的路径上的结点都必须包含s树中结点a
然后规定某个结点的基数就是它所包含的s树结点的个数，然后整个树的基数就是所有结点中最大的基数
现在就想让树的基数最小。
最后输出的是t树中每个结点包含了哪些s树中结点，以及t树中的边

这个需要手画一下。
然后不难得知，其实只要把s树中的每条边得两个结点，作为t树中的新结点即可
就是一个边对应一个结点
然后连接的方法类似于多叉树转换二叉树
我们先把每个边对应成一个结点。
我刚开始的想法是把根节点的儿子们与根组成的边对应的结点依次连接起来，然后其他结点的（儿子们与其父亲的边对应的结点）都跟（父亲结点与父亲的父亲结点组成的边对应的结点）相连
后来发现，只需要：
每个结点的儿子们与其父亲组成的边所对应的结点依次相连，（大儿子连二儿子，二儿子连三儿子）
大儿子与父亲组成的边对应的结点还要与（父亲结点与父亲的父亲结点组成的边对应的结点）相连
当然如果往上没有父节点了就不用连了。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100050
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

vector<int >edge[MAX];
int n;
int a[MAX],b[MAX];
int main()
{
    int i,j;
    while(cin >> n)
    {
        for(i=1; i<=n; i++)
            edge[i].clear();
        for(i=1; i<n; i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            edge[a[i]].push_back(i);
            edge[b[i]].push_back(i);
        }
        cout << n-1 << endl;
        for(i=1; i<n; i++)
        {
            printf("2 %d %d\n",a[i],b[i]);
        }
        for(i=1; i<=n; i++)
        {
            for(j=0; j<edge[i].size()-1; j++)
                printf("%d %d\n",edge[i][j],edge[i][j+1]);
        }
    }
    return 0;
}

E.

最小费用最大流，现在真心不会，把代码贴过来也没用，搞费用流时再来做这题.........