codeforces - 808 (div2)

谁借莪１个温暖的怀抱￠ 2023-10-11 13:26 50阅读 0赞

A.把这个数+1,如果符合条件就符合条件了，不符合就把最高位 + 1，其余位置0

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

B.列几下就找到规律，每个数加的次数是呈阶梯状的，例如 1 2 3 3 3 3 3 2 1,阶梯顶的值由星期数和K的最小值决定

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

C.先全部装一半，然后从大杯子往小杯子依次把剩下的水倒完，倒不完的和水不够的都是有问题的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

D.求出前缀和,枚举移动的数字t，然后二分在数字左端寻找pre\[i\] + t = sum的i，二分在右寻找pre\[i\] - t = sum的i

找到一次就是YES

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

E.感觉是个dp，我的做法肯定不是正解。

把三种重量的背包分类，按照价值从大到小排序然后求出前缀和,那么一定是在1，2，3中选择a,b,c个物品，答案是pre\[a\] + pre\[b\] + pre\[c\]

但是枚举是个O(n²),不能直接做。

所以直接上了模拟退火,模拟a,b,c指针的移动寻找最大值,洗了洗手交了一发就AC了

注：交下面的代码一遍可能A不了，需要洗洗手多交一边

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

F.题目的导向很明显,二分level或者将level排序依次更新答案。

先考虑2分level,如果将题目的意思换一种方式说:对于ci和为质数的两张卡片，必须至少放弃其中一张。

再配上N这个100的范围,思路就呼之欲出了

这是一个类似最大权闭合子图的网络流,建图的方法稍微和最大权闭合子图有些出入

拆所有点i为i和i + N

将所有点S向i连边，容量为p，将所有点i + N向T连边,然后对于每一对和为质数的点i,j,从i - j + N连边，容量为INF

最后整张图最大流的一半就是不得不放弃的最小权值，将总权值减去他和K比较即可check成功

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double eps = 1e-9;
    const int maxn = 1010;
    const int maxm = 2e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    bool isprime[maxm];
    void init(){
        for(int i = 2; i < maxm; i ++) isprime[i] = 1;
        for(int i = 2; i < maxm;  i ++){
            if(!isprime[i]) continue;
            for(int j = i + i; j < maxm; j += i){
                isprime[j] = 0;
            }
        }
    }
    struct Dinic{
        struct Edge{
            int from,to,next,cap,flow;
            Edge(){}
            Edge(int from,int to,int next,int cap,int flow):from(from),to(to),next(next),cap(cap),flow(flow){}
        }edge[maxm * 2];  
        int n,s,t,head[maxn],tot;
        int dep[maxn],cur[maxn];
        void init(int n,int s,int t){
            this->n = n; this->s = s; this->t = t; 
            tot = 0;
            for(int i = 0 ; i <= n ; i ++) head[i] = -1;
        }
        inline void add(int s,int t,int w){
            //cout << s << ' ' << t << " " << w << endl;
            edge[tot] = Edge(s,t,head[s],w,0);
            head[s] = tot++;
            edge[tot] = Edge(t,s,head[t],0,0);
            head[t] = tot++;
        }
        inline bool BFS(){
            for(int i = 0 ; i <= n ; i ++) dep[i] = -1;
            dep[s] = 1;
            queue<int>Q; Q.push(s);
            while(!Q.empty()){
                int u = Q.front(); Q.pop();
                for(int i = head[u]; ~i ; i = edge[i].next){
                    int v = edge[i].to;
                    if(~dep[v] || edge[i].flow >= edge[i].cap) continue;
                    dep[v] = dep[u] + 1;
                    Q.push(v);
                }
             }
             return ~dep[t];
        }
        inline int DFS(const int& u,int a){
            if(u == t || !a) return a;
            int flow = 0;
            for(int &i = cur[u]; ~i ; i = edge[i].next){
                int v = edge[i].to;
                if(dep[v] != dep[u] + 1) continue;
                int f = DFS(v,min(a,edge[i].cap - edge[i].flow));
                if(!f) continue;
                edge[i ^ 1].flow -= f;
                edge[i].flow += f; 
                a -= f;
                flow += f;
            }
            return flow;
        }
        inline int maxflow(){
            return maxflow(s,t);
        }
        inline int maxflow(int s,int t){
            int flow = 0;
            while(BFS()){
                for(int i = 0; i <= n ; i ++) cur[i] = head[i];
                flow += DFS(s,INF);
            }
            return flow;
        }
    }g;
    struct Node{
        int p,c,l;
    }node[110];
    bool cmp(Node a,Node b){
        return a.l < b.l;
    }
    bool check(int m){
        int S = N + N + 1,T = N + N + 2;
        g.init(T,S,T); LL sum = 0;
    //    if(m == 4){
    //        puts("bug");
    //    }
        for(int i = 1; i <= N ; i ++){
            if(node[i].l > m) break;
            sum += node[i].p * 2;
            g.add(S,i,node[i].p); g.add(i + N,T,node[i].p);
            for(int j = 1; j <= N ; j ++){
                if(i == j) continue;
                if(node[j].l > m) break;
                if(isprime[node[i].c + node[j].c]) g.add(i,j + N,INF);
            }
        }
        int x = g.maxflow(); 
        return (sum - x) >= M * 2;
    }
    int solve(){
        int l = 1,r = N;
        int ans = -1;
        while(l <= r){
            int m = l + r >> 1;
            if(check(m)){
                ans = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
    int main(){
        Sca2(N,M); init();
        for(int i = 1; i <= N ; i ++) Sca3(node[i].p,node[i].c,node[i].l);
        sort(node + 1,node + 1 + N,cmp);
        Pri(solve());
        return 0;
    }

dp\[i\]表示到这个\[1 - i\]范围内的字符串A最多可以匹配多少B,dp2\[i\]表示最后一个字符串是以i结尾的情况下,\[1-i\]范围内的字符串最多可以匹配多少B

那么先通过跳next指针的方式更新dp\[2\],然后dp\[i\] = max(dp\[i - 1\],dp2\[i\])

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

转载于:https://www.cnblogs.com/Hugh-Locke/p/11214567.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif