2022/2/7

P1251 餐巾计划问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

建模方法参考： 题解 P1251 [餐巾计划问题] - Mark_ZZY 的博客 - 洛谷博客 (luogu.com.cn)

拆点太妙了

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}


const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;

ll n,T,k,a[qs],b[qs];

ll s,t,p,head[qs],nxt[qs],val[qs],dis[qs],to[qs];

void add(int fx,int tx,int dx,int cx){
    to[p]=tx;
    dis[p]=dx;
    nxt[p]=head[fx];
    val[p]=cx;
    head[fx]=p++;
}

void ins(int u,int v,int w,int c){
//  cout<<"u="<<u<<" v="<<v<<" w="<<w<<" c="<<c<<"\n"; 
    add(u,v,w,c);
    add(v,u,0,-c);
}
int inq[qs],d[qs],pre[qs];

bool spfa(){
    for(int i=0;i<=n*2+1;++i){
        inq[i]=0;d[i]=inf,pre[i]=-1;
    }
    d[s]=0;inq[s]=1;
    queue<int> q; q.push(s);
    while(q.si){
        int u=q.front(); q.pop();
        inq[u]=0;
        for(int i=head[u];i!=-1;i=nxt[i]){
            if(dis[i]){//spfa是以费用val求最短路的，但流量不能忽略 
                int v=to[i];
            //  cout<<"v="<<v<<"\n";
                if(d[u]+val[i]<d[v]){
                    d[v]=d[u]+val[i];
                    pre[v]=i;
                //  cout<<"v="<<v<<" i="<<i<<"\n";
                    if(!inq[v]){
                        q.push(v);
                        inq[v]=1;
                    }
                }
            }
        }
    }
    return pre[t]!=-1;
}

void costflow(){//计算最小费用最大流 
    ll ret=0,ans=0;
    while(spfa()){
        //cout<<"***\n";
        ll flow=inf;
        
        for(int i=t;i!=s;i=to[pre[i]^1]){
            //计算当前增广路的最小流量 
            //cout<<"i="<<i<<" to="<<to[pre[i]^1]<<"\n";
            flow=min(dis[pre[i]],flow);
        }
        ans+=flow;
        for(int i=t;i!=s;i=to[pre[i]^1]){
            dis[pre[i]]-=flow;
            dis[pre[i]^1]+=flow;
            ret+=val[pre[i]]*flow;
        }
    }
    cout<<ret<<"\n";
}

void build_map(){
    memset(head,-1,sizeof(head));
    s=0,t=2*n+1;
    // 源点s向每个白天连一条 {inf,p} 的边，代表第i天可以从源点购买 
    for(int i=1;i<=n;++i) ins(s,i,inf,b[1]);
    // 每个白天向汇点 t 连一条{a[i],0} 的边，流量满即满足第i天 
    for(int i=1;i<=n;++i) ins(i,t,a[i],0);
    // 源点 s 向每天晚上连一条 {a[i],0} 的边，代表会往这天晚上送 a[i]条脏毛巾 
    for(int i=n+1;i<=n+n;++i) ins(s,i,a[i-n],0);
    // 第i天晚上向第 i+1 晚上连一条{inf,0} 的边，代表这天的脏毛巾回流到下一天 
    for(int i=n+1;i<n+n;++i) ins(i,i+1,inf,0); 
    //第i天晚上向 i+b[1] 天早上连一条 {inf,b[3]}的边，代表洗好的 
    for(int i=n+1;i<=n+n;++i) {
        int f1=i-n+b[2],f2=i-n+b[4];
        if(f1<=n) ins(i,f1,inf,b[3]);
        if(f2<=n) ins(i,f2,inf,b[5]);
    } 
    
}


int main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read(); 
    for(int i=1;i<=5;++i) b[i]=read();
    
    build_map();
    costflow();
    return 0;
}


/*

*/

方格填色 (nowcoder.com)

矩阵快速幂优化状压dp

把行列颠倒，先考虑状压dp,\(f[i][j]\)表示第i行状态为j的方案数，状态转移方程就是$f[i][j]+=f[i-1][j1] (j1|j==0 && j!=j1) $

由于行数 \(n<=1e18\),暴力不可取。

由于状态转移成线性关系，考虑矩阵快速幂。

关系矩阵可根据 $ (j1|j==0 && j!=j1)$构造

关系矩阵自乘n-1次中所有数的总和即是答案

(可以把矩阵快速幂扔到校赛去（逃

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define si size()
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}


const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;
int n,m;
struct Matrix {//矩阵初始化，乘法重载
    int a[40][40];//2^5只有32，开40*40足够
    Matrix()
    {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = 0;
            }
        }
    }
    Matrix operator * (const Matrix& Ma_) const
    {
        Matrix res;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * Ma_.a[k][j] % mod) % mod;
                }
            }
        }
        return res;
    }
};
Matrix quickpow(Matrix res,Matrix sta, ll b)//快速幂板子
{
    while (b > 0)
    {
        if (b & 1) res = res * sta;
        sta = sta * sta;
        b >>= 1;
    }
    return res;
}

Matrix f,p;
void build_M(){
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(i==j||(i&j)!=0) f.a[i][j]=0;
            else f.a[i][j]=1;
        }
    }
    for(int i=0;i<n;++i) p.a[i][i]=1;
}

signed main(){
    n=read(),m=read();
    n=(1<<n);
    build_M();
    f=quickpow(p,f,m-1);
    ll ans=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            ans=(ans+f.a[i][j])%mod;
        }
    } 
    ans=(ans+mod)%mod;
    cout<<ans<<"\n";
    
}

Problem - B - Codeforces (Unofficial mirror site, accelerated for Chinese users)

注意到 + 或 xor 一个数对整体来说改变的奇偶性是一样的

那就所有的数加起来再加x，跟y的奇偶性作对比即可

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
 
 
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;
 
 
ll n,x,y,T,a[qs],b[qs]; 
int main(){
    T=read();
    while(T--){
        n=read(),x=read(),y=read();
        ll fx,sum=0;
        for(int i=1;i<=n;++i){
            fx=read();
            sum+=fx;
        }
        x+=sum;
        if(x&1){
            if(y&1) cout<<"Alice\n";
            else cout<<"Bob\n"; 
        }
        else{
            if(!(y&1)) cout<<"Alice\n";
            else cout<<"Bob\n"; 
        }
    }
    
    
    return 0;
}

Problem - D - Codeforces (Unofficial mirror site, accelerated for Chinese users)

先随便指定两个数不变，n-2次询问其他数，得到一个最大值。

根据这个最大值的下标，再n-2次去找最大值，找到的下标即是答案。

（有些特殊情况需讨论

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}


const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;

map<int,int> mp;
ll n,T,k;
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        int m=-1,id,x;
        mp.clear();
        for(int i=3;i<=n;++i){
            cout<<"? 1 "<<"2 "<<i<<"\n";
            fflush(stdout);
            cin>>x;
            mp[x]++;
            if(x>m){
                m=x;
                id=i;   
            }
        }
        int fg=0;
        if(mp.si==1){
            fg=1;
//          cout<<"!1 2\n";
//          fflush(stdout);
//          continue;
        }
        int m1=-1;mp.clear();
        int f;
        for(int i=2;i<=n;++i){
            if(i==id) continue;
            cout<<"? 1 "<<id<<" "<<i<<"\n";
            fflush(stdout);
            cin>>x;
            mp[x]++;
            if(x>m1){
                m1=x;
                f=i;
            }
        }
        if(fg&&m==m1){
            cout<<"! 1 2\n";
            fflush(stdout);
            continue;
        }
        if(mp.si==1){
            cout<<"! 1 "<<id<<"\n";
            fflush(stdout);
            continue;
        }
        cout<<"! "<<f<<" "<<id<<"\n";
        fflush(stdout);
    }
    
    
    return 0;
}

Problem - E - Codeforces (Unofficial mirror site, accelerated for Chinese users)

欧拉回路

看了大佬博客了解了思想，明天码一下。

参考博客： Fair Share （构造+欧拉回路）

（

每日分享

【派大星】loser－当一个粉色的失败者有什么意思_哔哩哔哩_bilibili

当梦醒时分我该启程