codeforces

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

#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
", x)
#define Prl(x) printf("%lld
",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 = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
LL N,M,K;
int cul(LL x){
    int ans = 0;
    while(x){
        if(x % 10) ans++;
        x /= 10;
    }
    return ans;
}
int main(){
    Scl(N);
    LL x = N + 1;
    int num = cul(x);
    if(num == 1){
        Pri(1);
        return 0;
    }
    int p = 0;
    do{
        p++;
        x /= 10;
    }while(x >= 10);
    x++;
    for(int i = 0 ; i < p ;i ++) x *= 10;
    Prl(x - N);
    return 0;
}
A

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

#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
", x)
#define Prl(x) printf("%lld
",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 = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
long double a[maxn];
int main(){
    Sca2(N,M);
    long double sum = 0;
    for(int i = 1; i <= N; i ++){
        scanf("%Lf",&a[i]); 
        sum += a[i] * min(min(min(i,N - i + 1),M),N - M + 1);
    } 
    printf("%.10Lf",sum / (N - M + 1));
    return 0;
}
B

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

#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
", x)
#define Prl(x) printf("%lld
",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 = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
PII a[maxn];
int b[maxn];
int ans[maxn];
int main(){
    Sca2(N,M); int sum = 0;
    for(int i = 1; i <= N ; i ++) Sca(a[i].fi),a[i].se = i;
    sort(a + 1,a + 1 + N);
    for(int i = 1; i <= N ; i ++){
        b[i] = a[i].fi / 2;
        if(a[i].fi & 1) b[i]++;
        M -= b[i];
    }
    if(M < 0){
        puts("-1");
        return 0;
    } 
    for(int i = N; i >= 1 && M; i --){
        int t = min(a[i].fi - b[i],M);
        b[i] += t;
        M -= t;
    }
    if(M){
        puts("-1");
        return 0;
    }
    for(int i = 1; i <= N ; i ++) ans[a[i].se] = b[i];
    for(int i = 1; i <= N ; i ++){
        printf("%d ",ans[i]);
    }
    return 0;
}
C

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

找到一次就是YES

#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
", x)
#define Prl(x) printf("%lld
",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 = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9; 
int a[maxn];
LL pre[maxn];
int N;
LL sum;
bool check(int t)
{
    int l = 0;
    int r = t - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(pre[mid] + a[t] < sum) l = mid + 1;
        else if(pre[mid] + a[t] > sum) r = mid - 1;
        else return true;
    }
    l = t; r = N;
    while(l <= r){
        int mid = (l + r) / 2;
        if(pre[mid] - a[t] < sum) l = mid + 1;
        else if(pre[mid] - a[t] > sum) r = mid - 1;
        else return true;
    }
    return false;
    
}
int main()
{
    Sca(N);
    sum = 0;
    for(int i = 1; i <= N ; i ++){
        scanf("%d",&a[i]);
        sum += a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    if(sum & 1){
        printf("NO
");
        return 0;
    }
    sum /= 2; bool flag = 0;
    for(int i = 1; i <= N && !flag; i ++) if(check(i)) flag = 1;
    if(flag) printf("YES
");
    else printf("NO
");
    return 0;
}
D

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

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

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

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

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

#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
", x)
#define Prl(x) printf("%lld
",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 = 1e5 + 10;
const int maxm = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
LL pre[4][maxn],cnt[4];
vector<LL>Q[4];
bool cmp(LL a,LL b){
    return a > b;
}
LL ans,ansa,ansb,ansc;
LL cul(LL a,LL b,LL c){
    if(a + 2 * b + 3 * c > M) return 0;
    return pre[1][a] + pre[2][b] + pre[3][c];
}
const double delta = 0.999;
void s_a(){
    double t = 30000;
    int a = ansa,b = ansb,c = ansc;
    while(t > 1e-14){
        int atmp = a + (rand() * 2 - RAND_MAX) * t; atmp = ((atmp % (Q[1].size() + 1)) + Q[1].size() + 1) % (Q[1].size() + 1);
        int btmp = b + (rand() * 2 - RAND_MAX) * t; btmp = ((btmp % (Q[2].size() + 1)) + Q[2].size() + 1) % (Q[2].size() + 1);
        int ctmp = c + (rand() * 2 - RAND_MAX) * t; ctmp = ((ctmp % (Q[3].size() + 1)) + Q[3].size() + 1) % (Q[3].size() + 1);
        LL new_ans = cul(atmp,btmp,ctmp);
        LL DE = new_ans - ans;
        if(DE > 0){
            ansa = a = atmp; ansb = b = btmp; ansc = c = ctmp;
            ans = new_ans;
        }else if(-exp(-DE / t) * RAND_MAX > rand()){
            a = atmp; b = btmp; c = ctmp;
        }
        t = t * delta;
    }
}
void SA(){
    s_a();s_a();
    s_a();s_a();
    s_a();s_a();
}
int main(){
    Sca2(N,M); srand(time(NULL));
    for(int i = 1; i <= N ; i ++){
        LL w = read(),t = read();
        Q[w].pb(t);
    }
    for(int i = 1; i <= 3; i ++) sort(Q[i].begin(),Q[i].end(),cmp);
    for(int i = 1; i <= 3; i ++){
        for(int j = 0 ; j < Q[i].size(); j ++){
            pre[i][j + 1] = pre[i][j] + Q[i][j];
        }
    }
    ansa = ansb = ansc = 0;
    SA(); //ACACAC
    Prl(cul(ansa,ansb,ansc));
    return 0;
}
E

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成功

#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
", x)
#define Prl(x) printf("%lld
",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;
}
F

G.

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

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

#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
", x)
#define Prl(x) printf("%lld
",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 = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char A[maxn],B[maxn]; 
LL dp[maxn],dp2[maxn];
int nxt[maxn];
int N,M,K;
void kmp_pre(char x[],int m,int nxt[]){
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m ; i ++){
        while(j && x[i] != x[j + 1]) j = nxt[j];
        if(x[j + 1] == x[i]) j ++;
        nxt[i] = j;
    }
}
int main(){
    scanf("%s%s",A + 1,B + 1);
    N = strlen(A + 1),M = strlen(B + 1);
    kmp_pre(B,M,nxt);
//    for(int i = 1; i <= M ; i ++){
//        cout << nxt[i] << " ";
//    }
//    cout << endl;
    for(int i = M; i <= N ; i ++){
        bool flag = 1;
        for(int j = 1; j <= M; j ++){
            if(B[j] != A[i - M + j] && A[i - M + j] != '?') flag = 0;
        }
        if(!flag){
            dp[i] = dp[i - 1];
            continue;
        } 
        dp2[i] = max(dp2[i],dp[i - M] + 1);
        for(int j = nxt[M]; j ; j = nxt[j]){
            dp2[i] = max(dp2[i],dp2[i - M + j] + 1);
        }
        dp[i] = max(dp[i - 1],dp2[i]);
    }
    Prl(dp[N]);
    return 0;
}
G
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Hugh-Locke/p/11214567.html