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, |
A, |
B | 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;
}
标签:25,cnt,12,NOIP,MIN,int,MAXN,MAXM,include
From: https://www.cnblogs.com/int-R/p/NOIP-A-25.html