首页 > 其他分享 >NOIP 模拟12(NOIP A层联测25)

NOIP 模拟12(NOIP A层联测25)

时间:2023-11-06 17:55:06浏览次数:42  
标签:25 cnt 12 NOIP MIN int MAXN MAXM include

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=1 w=0
A B,D A,C
B A,D B,C
C A,B,D C
D NONE A,B,C,D

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

w=1 w=0
A B,D A,D
B A,D B,D
C A,B,D A,B,C,D
D NONE D

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

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

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

w=1 w=0
A B,D A,D
B A,D B,D
C A,B,D A,B,C,D
D NONE D

所以就直接黑白染色,要求 \(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;
}

标签:25,cnt,12,NOIP,MIN,int,MAXN,MAXM,include
From: https://www.cnblogs.com/int-R/p/NOIP-A-25.html

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt (129)-- 算法导论11.1 4题
    四、用go语言,我们希望在一个非常大的数组上,通过利用直接寻址的方式来实现一个字典。开始时该数组中可能包含一些无用信息,但要对整个数组进行初始化是不太实际的,因为该数组的规模太大。请给出在大数组上实现直接寻址字典的方案。每个存储对象占用O(1)空间;SEARCH、INSERT和DELETE操......
  • SFTP无法连接 Connection closed by server with exitcode 127
    命令:Pass:************状态:Connectedto66.77.88.99错误:Connectionclosedbyserverwithexitcode127错误:无法连接到服务器 解决方法:vi/etc/ssh/sshd_config    其中:“Subsystemsftp/usr/libexec/sftp-server” 将其修改为正确的sftp-server路径Subsystem......
  • Oracle imp 导入数据出现 ORA-12560
    错误如下:D:\software\xfwebdb2015-05-11\autobackup>impImport:Release10.2.0.1.0-Productionon星期三5月1319:36:102015Copyright(c)1982,2005,Oracle. Allrightsreserved.用户名:zfzb口令:IMP-00058:遇到ORACLE错误12560ORA-12560:TNS:协议适配器错误IM......
  • Windows 下 ORA-12560: TNS: 协议适配器错误的问题
    Windows下ORA-12560:TNS:协议适配器错误的问题原因有三个: 1.监听服务没有起起来。windows平台个一如下操作:开始---程序---管理工具---服务,打开服务面板,启动oraclehome92TNSlistener服务。 2.databaseinstance没有起起来。windows平台如下操作:开始---程序---管理工具---服务,......
  • 日记 2022.12.17:22年实验中学秋季训练 6
    A.gym103428m问有多少个长度为\(n\)的01串,其中有\(m\)个是1,且最长连续的1的长度恰好是\(k\)。十万。Trick1容斥系数怎么算?Trick2限制了这个串的长度和\(1\)的个数,这意味着什么?插板的东西是什么?solution错解明显不顾最长连续段限制答案是$g(n,m)=\bin......
  • AT2505板子调试
    1、连接J-Link  在这个目录下说命令找不到 JLinkGDBServer-deviceStar  sudodpkg-i*.deb 2、连接串口打印线(TX-RX,RX-TX,GND-GND)sudominicom-D/dev/ttyUSB0 打开串口调试窗口 3、仿真 注意:J-link一连接后会一直打印奇奇怪怪的乱码,不用管,刚连接后......
  • 【洛谷 P1046】[NOIP2005 普及组] 陶陶摘苹果 题解(比较)
    [NOIP2005普及组]陶陶摘苹果题目描述陶陶家的院子里有一棵苹果树,每到秋天树上就会结出个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。现在已知个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的......
  • Nodejs的安装以及配置(node-v12.16.1-x64.msi)
    Nodejs的安装以及配置1、安装node-v12.16.1-x64.msi点击安装,注意以下步骤本文设置nodejs的安装的路径:D:\soft\nodejs  继续点击next,选中AddtoPATH,旁边的英文告诉我们会把环境变量给我们配置好 当然也可以只选择Node.jsruntime,根据自己需要选择安装 下面如......
  • 异常Couldn’t connect to host, port: smtp.qq.com, 25
    com.sun.mail.util.MailConnectException:Couldn’tconnecttohost,port:smtp.qq.com,25;timeout-1阿里云处于安全考虑,TCP25端口默认被封禁。可以向阿里云申请解封,也可以改为ssl加密465端口发送。465端口发送主要代码:Propertiesprops=newProperties();props.......
  • /var/lib/docker/overlay2/41a765b3cfaa278a67414c5b89234adfdebac7182d4bcd1e7c8a2c6
    现象:Error:Errorresponsefromdaemon:errorcreatingoverlaymountto/var/lib/docker/overlay2/41a765b3cfaa278a67414c5b89234adfdebac7182d4bcd1e7c8a2c6ac250dfb7-init/merged:nosuchfileordirectory原因:由于Docker存储空间中的一些残留文件或损坏的文件系统引......