省选联考17

三道题三道题三道题!!!
起床晚了导致晚答一个小时（（（

A.开心消消乐 game.cpp

之前在 acc 考到过原题，但是但是太菜了，不明白 dp套dp，所以还是不会，只会愚蠢的白给的20pts的普通dp

实际得分：0 （因为压根没写）

应该得分：20

正解就是首先考虑没有 ? 怎么做，可以考虑到一个小trick:把变换前两位看作函数类型，最后一位看作自变量，这样令 \(g_{i,00/01/10/11}\) 为前 \(i\) 位经过操作后剩下的一个变换为 \(00/01/10/11\) 的情况是否存在，那么就有两种转移：叠加变换也就是把下一次合并继续往后拖 和 把第一位结算并把第二位加入，最后在最后一位判断一下。

如果有 \(?\) 的话就是一个显而易见的 dp套dp 了，可以用 \(f_{i,2^4}\) 表示方案数，具体地：第一位表示前 \(i\) 位，第二维表示 \(g_{i,00/01/10/11}\) 的状态。
最后一位结算一下答案

Talk is cheap,show you my Code!!!

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int p=998244353;
using ll=long long;
char str[N];
int n;
int s[N];
int bas[4];
int trans[4][4];
ll f[N][16];
void solve()
{
    memset(bas,0,sizeof(bas));
    cin>>str;for(int i=0;i<=1;i++)
    for(int j=0;j<=1;j++)for(int k=0,val;k<=1;k++)
    val=str[i*4+j*2+k]-'0',bas[k*2+j]+=val<<i;
    memset(str,0,sizeof(str));
    cin>>str+1;n=strlen(str+1);
    for(int i=1;i<=n;i++)s[i]=(str[i]=='?')?-1:(str[i]-'0');
    for(int i=0;i<=3;i++)for(int j=0;j<=3;j++)
        trans[i][j]=((i>>((j>>1)&1))&1)*2+((i>>(j&1))&1);
    for(int i=2;i<=n;i+=2)for(int j=0;j<=15;j++)f[i][j]=0;
    vector<int> vec;
    for(int i=2;i<=n;i+=2)
    {
        vec.clear();
        if(s[i-1]==-1&&s[i]==-1)for(int j=0;j<=3;j++)vec.push_back(j);
        else if(s[i-1]==-1)for(int j=0;j<=1;j++)vec.push_back(j*2+s[i]);
        else if(s[i]==-1)for(int j=0;j<=1;j++)vec.push_back(s[i-1]*2+j);
        else vec.push_back(s[i-1]*2+s[i]);
        if(i==2){for(auto ele:vec)f[i][1<<bas[ele]]++;continue;}
        for(auto ele:vec)
        {
            for(int sta=0;sta<=15;sta++)
            {
                int nxt=0;
                if(!f[i-2][sta])continue;
                for(int j=0;j<=3;j++)
                {
                    if(!((sta>>j)&1))continue;
                    nxt|=1<<trans[j][bas[ele]];
                    nxt|=1<<bas[((j>>((ele>>1)&1))&1)*2+(ele&1)];
                }
                f[i][nxt]=(f[i][nxt]+f[i-2][sta])%p;
            }
        }
    }
    vec.clear();
    if(s[n]==-1)vec.push_back(0),vec.push_back(1);
    else vec.push_back(s[n]);
    ll ans=0;
    for(auto ele:vec)
    {
        for(int i=0;i<=15;i++)
        {
            if(!f[n-1][i])continue;
            bool fl=0;
            for(int j=0;j<=3;j++)if((i>>j)&1)fl|=(j>>ele)&1;
            if(fl)ans=(ans+f[n-1][i])%p;
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;while(t--)solve();
    return 0;
}

B.树上的棋局 tree.cpp

由于对博弈论不熟导致浪费了很多时间，不过好在最后会 \(O(nm)\) ，但是脑子一短路忘记打 \(x=1\) 的部分分了。。。

实际得分：36

应该得分：52

正解不会

C.社会黄油飞 socialbutterfly.cpp

忘记网络流也没想到贪心，最失败的一集，哎说白了还是欠练。。。

实际得分：30

应该得分：10

鉴定为，数据太水了（
正解转化+网络流
但是看到一个神奇的贪心做法：每次删除度数最小的点，然后过程中判断，复杂度 \(O(n\log n+m\log m)\)
暂时不会证明（也就是说可能假了（

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int N=2005,M=6005;
int n,m,lim;
int ans;
int deg[N];
vector<int> edge[N];
set<pii> s;
int main()
{
    freopen("socialbutterfly.in","r",stdin);
    freopen("socialbutterfly.out","w",stdout);
    cin>>n>>m>>lim;
    for(int i=1,u,v;i<=m;i++)cin>>u>>v,deg[u]++,
    deg[v]++,edge[u].push_back(v),edge[v].push_back(u);
    ans=m;
    for(int i=1;i<=n;i++)s.insert((pii){deg[i],i});
    for(int i=n;i>=1;i--)
    {
        if(ans>1ll*lim*(i-1))return (cout<<"Yes\n",0);
        int u=(*s.begin()).second;
        ans-=deg[u];
        s.erase((pii){deg[u],u});
        for(auto v:edge[u])
        {
            if(s.find((pii){deg[v],v})==s.end())continue;
            s.erase((pii){deg[v],v});
            deg[v]--;
            s.insert((pii){deg[v],v});
        }
    }cout<<"No\n";
    return 0;
}

就这些啦！！！
\(20+52+10=82\rightarrow0+36+30=66\)
评价为：菜