100+100+30+100，T4 自己写了 Check 最后一分钟发现 Check 锅了，赌了一发替换了部分分，赢！

A.构造

默认 \(n\geq 3,n\in \{2x+1,x\in N\},m\geq 4\)。

考虑构造

rrrrr---
yyyyy---
xxxxx---
yyyyy---
rrrrr---
yyyyy---
xxxxx---
--------

这样有 \(\dfrac{n-1}{2}\times (3m-4)\) 个数，最多有 \(2204\) 个，然后最后再加一行可以同样 ryxyryx 的构造，不会与先前有冲突，可以再加 \(\lfloor \dfrac{m-1}{2}\rfloor\leq 19\) 个数，\(2223\) 个刚好够。

再考虑可能还要删去一些，考虑处理第 \(n\) 行，将一些 \(r\) 或 \(x\) 改成 \(y\)，修改左两列或右两列会少 \(2\) 个，中间的会少 \(3\) 个，再加上上文说的最后可以再加 \([1,\lfloor \dfrac{m-1}{2}\rfloor]\) 个数，可以覆盖所有情况（最后一行的空位也都填上 \(y\)）。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int main()
{
    freopen("ryx.in","r",stdin);
    freopen("ryx.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int x=3;x<=40;x+=2)//枚举行数
    for(int y=4;y<=40;++y)//枚举列数
    for(int i=0;i<=4;++i)//枚举删掉几个 2
    for(int j=0;j<=y-4;++j)//枚举删掉几个 3
    for(int k=0;k<=(y-1)/2;++k)//枚举最后再加一行中加几个
    if((x-1)/2*(3*y-4)-2*i-3*j+k==n)
    {
        cout<<x+(k?1:0)<<' '<<y<<'\n';
        char ch[4]={'r','y','x','y'};
        for(int A=1;A<=x-1;++A)
        {
            for(int B=1;B<=y;++B)
                cout<<ch[(A-1)%4];
            cout<<'\n';
        }
        for(int B=1;B<=y;++B)
        {
            if(B<=2||B>y-2)
            {
                if(i) cout<<'y',--i;
                else cout<<ch[(x-1)%4];
            }
            else
            {
                if(j) cout<<'y',--j;
                else cout<<ch[(x-1)%4];
            }
        }
        cout<<'\n';
        if(k)
        {
            for(int B=1;B<=2*k+1;++B) cout<<ch[(B-1)%4];
            for(int B=2*k+2;B<=y;++B) cout<<'y';cout<<'\n';
        }
        return 0;
    }
    return 0;
}

B.游戏

二分答案 \(mid\)，最优一定是使所有 \(i\in[1,n],a_i>mid\) 的这些 \(i\) 的期望变成 \(mid\)，即 \((1-p_i)\times a_i=mid\)。

然后判断 \(\sum p_i\) 是否小于等于 \(1\) 即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
const int MAXN=35;
const long double eps=1e-14;
int n;long double a[MAXN];
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;long double l=0,r=0;
    for(int i=1;i<=n;++i) cin>>a[i],r=max(r,a[i]);
    while(l+eps<r)
    {
        long double mid=(l+r)/2,cur=0;
        for(int i=1;i<=n;++i)
        {
            if(a[i]<=mid) continue;
            cur+=1-mid/a[i];
        }
        (cur<=1)?r=mid:l=mid;
    }
    cout<<fixed<<setprecision(9)<<l<<'\n';
    return 0;
}

C.数数

恼了，没改动。

D.滈葕

非“生物 \(+\) 2-SAT”做法，但感觉那个 2-SAT 挺妙的。

下表表示在 \(u=A/B/C/D,w=1/0\) 时，\(v\) 可以的取值。

感觉不好看（赛时我真的是因为感觉不好看）考虑将所有 \(w=0\) 的边交换方向。

先考虑 \(C,D\)，贪心使它们越多越好（因为限制较松）。

因为 \(D\) 作为 \(v\) 时永远都可行，但是除了 \(w=1,u=D\)，所以只要从一个点开始遍历，其能遍历到的所有边都是 \(0\)，那么它就可以作为 \(D\)。于是 \(C\) 同理。这个 tarjan 缩点可做，但好像不必要缩点？

那么将已经确定 \(C,D\) 抽离出来，只保留剩下的点及之间的边，剩下的点一定 \(\in\{A,B\}\)。

所以就直接黑白染色，要求 \(w=1\) 的两个端点颜色不同，\(w=0\) 的两个端点颜色相同。

代码其实没必要那么长，这是赛时的，当时复制了两部分，可以简化的。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int MAXN=1e5+10,MAXM=1e6+10;
int n,m,x[MAXM],y[MAXM],z[MAXM];
int outo[MAXN],into[MAXN],ans[MAXN];
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],cnt;
inline void add(int x,int y,int v)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt,val[cnt]=v;return ;
}
void dfs(int x,int k,int fa=0)
{
    ans[x]=k;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(!ans[y]) dfs(y,(val[i])?3-k:k,x);
        else if((ans[y]!=ans[x])^val[i]) cout<<"NO\n",exit(0);
    }
    return ;
}
namespace tarjan
{
    vector <int> v[MAXN];stack <int> s;queue <int> q;
    int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],cnt;
    int dfn[MAXN],MIN[MAXN],tot,dcc[MAXN],num;
    int into[MAXN];bool vis[MAXN],b[MAXN];
    inline void add(int x,int y,int v)
    {
        to[++cnt]=y,nxt[cnt]=head[x];
        head[x]=cnt,val[cnt]=v;return ;
    }
    void dfs(int x)
    {
        s.push(x),dfn[x]=MIN[x]=++tot,vis[x]=true;
        for(int y:v[x])
        {
            if(!dfn[y]) dfs(y),MIN[x]=min(MIN[x],MIN[y]);
            else if(vis[y]) MIN[x]=min(MIN[x],dfn[y]);
        }
        if(MIN[x]==dfn[x])
        {
            ++num;
            while(s.top()!=x)
                dcc[s.top()]=num,vis[s.top()]=false,s.pop();
            dcc[s.top()]=num,vis[s.top()]=false,s.pop();
        }
        return ;
    }
    inline void work()
    {
        for(int i=1;i<=m;++i) v[x[i]].push_back(y[i]);
        for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i);
        for(int i=1;i<=m;++i)
            if(dcc[x[i]]!=dcc[y[i]]) add(dcc[x[i]],dcc[y[i]],z[i]),into[dcc[y[i]]]++;
            else if(z[i]==1) b[dcc[x[i]]]=true;
        for(int i=1;i<=num;++i) if(!into[i]) q.push(i);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=nxt[i])
            {
                int y=to[i];b[y]|=(b[x]|val[i]);
                if(!(--into[y])) q.push(y);
            }
        }
        for(int i=1;i<=n;++i) if(!b[dcc[i]]) ans[i]=3;
        return ;
    }
};
namespace tarjan2
{
    vector <int> v[MAXN];stack <int> s;queue <int> q;
    int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],cnt;
    int dfn[MAXN],MIN[MAXN],tot,dcc[MAXN],num;
    int into[MAXN];bool vis[MAXN],b[MAXN];
    inline void add(int x,int y,int v)
    {
        to[++cnt]=y,nxt[cnt]=head[x];
        head[x]=cnt,val[cnt]=v;return ;
    }
    void dfs(int x)
    {
        s.push(x),dfn[x]=MIN[x]=++tot,vis[x]=true;
        for(int y:v[x])
        {
            if(!dfn[y]) dfs(y),MIN[x]=min(MIN[x],MIN[y]);
            else if(vis[y]) MIN[x]=min(MIN[x],dfn[y]);
        }
        if(MIN[x]==dfn[x])
        {
            ++num;
            while(s.top()!=x)
                dcc[s.top()]=num,vis[s.top()]=false,s.pop();
            dcc[s.top()]=num,vis[s.top()]=false,s.pop();
        }
        return ;
    }
    inline void work()
    {
        for(int i=1;i<=m;++i) v[y[i]].push_back(x[i]);
        for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i);
        for(int i=1;i<=m;++i)
            if(dcc[x[i]]!=dcc[y[i]]) add(dcc[y[i]],dcc[x[i]],z[i]),into[dcc[x[i]]]++;
            else if(z[i]==1) b[dcc[y[i]]]=true;
        for(int i=1;i<=num;++i) if(!into[i]) q.push(i);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=nxt[i])
            {
                int y=to[i];b[y]|=(b[x]|val[i]);
                if(!(--into[y])) q.push(y);
            }
        }
        for(int i=1;i<=n;++i) if(!b[dcc[i]]) ans[i]=4;
        return ;
    }
};
int main()
{
    freopen("dopetobly.in","r",stdin);
    freopen("dopetobly.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x[i]>>y[i]>>z[i];
        if(!z[i]) swap(x[i],y[i]);
    }
    tarjan::work(),tarjan2::work();
    for(int i=1;i<=m;++i)
        if(!ans[x[i]]&&!ans[y[i]])
            add(x[i],y[i],z[i]),add(y[i],x[i],z[i]);
    for(int i=1;i<=n;++i) if(!ans[i]) dfs(i,1);
    cout<<"YES\n";
    for(int i=1;i<=n;++i) cout<<(char)(ans[i]-1+'A');
    cout<<'\n';return 0;
}

本栏目推荐文章
• P9871 [NOIP2023] 天天爱打卡
• NOIP2023vp
• NOIP2023 游记
• P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G(memset用法)
• [NOIP2005 提高组] 谁拿了最多奖学金
• P8868 [NOIP2022] 比赛 题解
• [NOIP2023] 词典
• P1010 [NOIP1998 普及组] 幂次方（十进制转二进制）（递归）
• [Luogu] P1058 [NOIP2008 普及组] 立体图
• 【题解】洛谷P1068 [NOIP2009 普及组] 分数线划定 （map）

NOIPnoip 2023 2023 noip noip 2001 游记noip noip 2022 p1036 noip 2002 p1002 noip 2002 2023 noip t2 游记noip 2023 nfls-noip