勉勉强强算是五题都出了

但是第五题的算法还是一知半解的状态

单纯在贴模板而已，回头重写

B. Young Table

英语捉急，发现是Special Judge后立马就出了。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int n,sum,aim;
int c[105];
struct node
{
    int shu;
    int x,y;
};
node s[10005];
int s2[10005];
int xx1[10005];
int yy1[10005];
int xx2[10005];
int yy2[10005];

bool cmp(int x,int y)
{
    return x < y; 
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&c[i]);
    sum = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c[i];j++)
        {
            scanf("%d",&s[sum].shu);
            s[sum].x = i;
            s[sum].y = j;
            s1[sum] = s[sum].shu;
            sum++;
        }
    }
    sort(s1,s1 + sum,cmp);
    aim = 0;
    for(int i=0;i<sum;i++)
    {
        while(s[i].shu != s1[i])
        {
            for(int j=i+1;j<sum;j++)
            {
                if(s[i].shu == s1[j])
                {
                    xx1[aim] = s[i].x;
                    yy1[aim] = s[i].y;
                    xx2[aim] = s[j].x;
                    yy2[aim] = s[j].y;
                    swap(s[i].shu,s[j].shu);
                    aim++;
                    break;
                }
            }
        }
    }
    printf("%d\n".aim);
    for(int i=0;i<aim;i++)
    {
        printf("%d %d %d %d\n",xx1[i],yy1[i],xx2[i],yy2[i]);
    }
    return 0;
}

C. Primes on Interval

一开始二分没写好

重写简化之后就好多了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

bool s[1000005];
int su[1000005];
int shu;
int aa,a,b,k,aim,lia;

void get(int x)
{
    memset(s,0,sizeof(s));
    shu = 0;
    s[0] = s[1] = 1;
    su[0] = su[1] = 0;
    for(int i=2;i<=x;i++)
    {
        if(s[i] == 0)
        {
            shu++;
            for(int j=i*2;j<=x;j+=i)
                s[j] = 1;
        }
        su[i] = shu;
    }
}

int main()
{
    scanf("%d%d%d",&a,&b,&k);
    get(b);
    //cout<<shu<<endl;
    if(shu - su[a - 1]< k)
    {
        printf("-1\n");
    }
    else
    {
        int high = b - a + 1;
        int low = 1;
        int mid,q;
        while(low < high)
        {
            mid = (low + high) / 2;
            q = 0;
            for(int i = a; i <= b - mid + 1;i++)
            {
                if(su[i + mid - 1] - su[i - 1] < k)
                {
                    q=1;
                }
            }
            if(q == 0)
            {
                high=mid;
            }
            else
            {
                low = mid + 1;
            }
        }
        printf("%d\n",high);
    }
    return 0;
}

D. T-decomposition

又是万恶的Special Judge。。早知道就写了。。还是英语问题。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> s[100005];

int main()
{
    int n,x,y,i,j;
    scanf("%d",&n);
    printf("%d\n",n-1);
    for(i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        s[x].push_back(i);
        s[y].push_back(i);
        printf("2 %d %d\n",x,y);
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<s[i].size(); j++)
        {
            printf("%d %d\n",s[i][j-1],s[i][j]);
        }
    }
    return 0;
}

E. Build String

听说是最小费用最大流，但是看着模板写完也没明白是怎么运转的。。回头重写

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#define MAXM 1111111
#define MAXN 11111
#define INF 1000000007
using namespace std;
struct EDGE
{
    int v, cap, cost, next, re;
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{
    e = ans = flow = 0;
    memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{
    edge[e].v = v;
    edge[e].cap = cap;
    edge[e].cost = cost;
    edge[e].next = head[u];
    edge[e].re = e + 1;
    head[u] = e++;
    edge[e].v = u;
    edge[e].cap = 0;
    edge[e].cost = -cost;
    edge[e].next = head[v];
    edge[e].re = e - 1;
    head[v] = e++;
}
bool spfa()
{
    int i, h = 0, t = 1;
    for(i = 0; i <= n; i ++)
    {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[src] = 0;
    que[0] = src;
    vis[src] = true;
    while(t != h)
    {
        int u = que[h++];
        h %= n;
        vis[u] = false;
        for(i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(edge[i].cap && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    que[t++] = v;
                    t %= n;
                }
            }
        }
    }
    if(dis[des] == INF) return false;
    return true;
}
void end()
{
    int u, p, mi = INF;
    for(u = des; u != src; u = edge[edge[p].re].v)
    {
        p = pre[u];
        mi = min(mi, edge[p].cap);
    }
    for(u = des; u != src; u = edge[edge[p].re].v)
    {
        p = pre[u];
        edge[p].cap -= mi;
        edge[edge[p].re].cap += mi;
        ans += mi * edge[p].cost;
    }
    flow += mi;
}
char str[111], req[11111];
int nt;
int tt[11111];
int ss;
void build()
{
    scanf("%s", req);
    scanf("%d", &nt);
    ss = strlen(req);
    for(int i = 0; i < ss; i++)
        tt[req[i] - 'a']++;
    src = 1;
    n = nt + 28;
    des = n;
    int v[33];
    int xy;
    for(int i = 0; i < nt; i++)
    {
        scanf("%s%d", str, &xy);
        int len = strlen(str);
        memset(v, 0, sizeof(v));
        int now = 2 + i;
        add(src, now, xy, 0);
        for(int j = 0; j < len; j++)
            v[str[j] - 'a']++;
        for(int j = 0; j < 26; j++)
            if(v[j]) add(now, nt + 2 + j, v[j], i + 1);
    }
    for(int i = 0; i < 26; i++)
        add(nt + 2 + i, des, tt[i], 0);
}
void MCMF()
{
    init();
    build();
    while(spfa()) end();
    if(flow != ss) printf("-1\n");
    else printf("%d\n", ans);
}

int main()
{
    MCMF();
    return 0;
}