脚本宝典收集整理的这篇文章主要介绍了NOIp模拟57，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
水博客太快乐了
RT
又没烤好。。。 考场上感觉还不错，但是一堆迷惑操作下来就没多少分了。。。。 原来的名字太丑被吐槽了。。。于是就改正常了。。。
先看 (T1) ，居然有送分题？狂喜。。。 再看 (T2) ，居然又是送分题？狂喜。。。 然而后来这两题都挂了。。。
看 (T3) ，这题意着实让人有点懵。。。没看懂，写了一个看似很正确的写法上去。。。 看 (T4) ，一开始理解错题意了，写了个假做法。。。后来看懂题，在原做法基础上加了个拓扑排序。。
感觉考的很不戳，坐等出分。。。
(t1 90pts + t2 60pts + t3 40pts + t4 0pts = 190pts)
本来题不是很难，考成这样也着实够菜了。。。
水题，自己怎么挂了回去好好反思。。。。 面壁思过。。。
前两个条件显然可以用 (map) 维护，考虑第三个条件。
第三个条件乍一看很复杂，先考虑暴力如何实现。不难想到暴力跳祖先，设当前点由集合 (P) 继承得到，那么若存在 (p_i, p_j) 有相同的祖先且 (p_i, p_j) 两点间没有祖先关系，则形成了一个菱形。
直接暴力跳祖先很有可能大力 (TLE) ，因此考虑用 (bITset) 优化，存下每个点的祖先节点集合即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
inline int read(){
int f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
int n;
char ch[N], ul[N][N];
bitset<N> s[N], ul1;
unordered_map<string, int > mp;
int main(void){
freoPEn("class.in", "r", stdin);
freopen("class.out", "w", stdout);
n=read();
while(n--){
bool flag=0;
scanf("%s", ch+1);
scanf("%s", ul[0]+1);
scanf("%s", ul[0]+1);
for(int i=0; ul[i][1]!=';'; ++i)
scanf("%s", ul[i+1]+1);
if(mp[ch+1]) { puts("greska"); continue; }
for(int i=0; ul[i][1]!=';'; ++i)
flag|=!mp[ul[i]+1];
if(flag) { puts("greska"); continue; }
for(int i=0; ul[i][1]!=';'; ++i) for(int j=i+1; ul[j][1]!=';'; ++j){
int k1=mp[ul[i]+1], k2=mp[ul[j]+1];
if((s[k1]&s[k2])!=ul1&&!s[k1][k2]&&!s[k2][k1]) flag|=1;
}
if(flag) { puts("greska"); continue; }
for(int i=0; ul[i][1]!=';'; ++i){
int k1=mp[ul[i]+1];
s[n][k1]=1; s[n]|=s[k1];
}
mp[ch+1]=n;
puts("ok");
}
return 0;
}
一道感觉比较有趣的题，然而并没有看懂题解。。。。
一开始没看懂题意，以为原图中所有度数为 (k) 的点都必定会属于一个 (k-degree) 子图，后来才发现原来是子图内所有点的度数都至少为 (k) 才可以，而与这个点在原图中的度数无关。。。
最开始写的是从高到低枚举度数，每次将 (k+1-degree) 子图加入一些点变成一张 (k-degree) 字图，然后用并查集维护联通性，同时维护点数、边数以及边界边数。 后来意识到度数为 (k) 的点不一定在一张 (k-degree) 子图中，于是想到先拓扑排序，求出每个点最大在哪张 (k-degree) 子图中，然后同样用上述方法维护。
然而考场上一时 (NT) 把可以用 (n) 个 (vector) 维护的东西写成了 (n) 个 (queue) ，于是大力 (MLE) 了。。。改了就过了。。。 血亏。。。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi First
#define se second
const int N=1e6+10;
const ll INF=0x7fffffffffffffff;
inline int read(){
int f=1, x=0; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
return f*x;
}
int n, m, n1, m1, b1, k1;
ll maxn=-iNF;
vector<int> l[N], ul[N], l1[N];
int deg[N], num[N];
pair<int, int> p[N];
vector<int> vec[N];
queue<int> q;
struct s{
int fa, siz, ed, sid;
}f[N];
int find(int x) { return f[x].fa==x ? x : f[x].fa=find(f[x].fa); }
inline void topsort(int k){
for(int v : vec[k])
if(!num[v]) q.push(v);
while(!q.empty()){
int u=q.front(); q.pop();
if(num[u]) continue;
ul[k].push_back(u); num[u]=k;
for(int v : l[u]){
if(num[v]) continue;
if(--deg[v]==k) q.push(v);
vec[deg[v]].push_back(v);
}
}
}
int main(void){
freopen("kdgraph.in", "r", stdin);
freopen("kdgraph.out", "w", stdout);
n=read(), m=read(); int x, y;
m1=read(), n1=read(), b1=read();
for(int i=1; i<=m; ++i){
x=read(), y=read(); ++deg[x], ++deg[y];
l[x].push_back(y); l[y].push_back(x);
p[i]=make_pair(x, y);
}
for(int i=1; i<=n; ++i) vec[deg[i]].push_back(i);
for(int i=1; i<=n; ++i) topsort(i);
for(int i=1; i<=n; ++i) f[i]=(s){ i, 1, 0, 0 }, l[i].clear();
for(int i=1; i<=m; ++i){
if(num[p[i].fi]!=num[p[i].se]) l[p[i].fi].push_back(p[i].se);
l[p[i].se].push_back(p[i].fi);
}
for(int k=n; k; --k){
if(ul[k].empty()) continue;
for(int u : ul[k]){
for(int v : l[u]){
int F1=find(u), f2=find(v);
if(f1==f2){
++f[f1].ed;
if(num[u]<num[v]) --f[f1].sid;
continue;
}
if(num[u]==num[v]){
f[f1].fa=f2; f[f2].siz+=f[f1].siz;
f[f2].sid+=f[f1].sid; f[f2].ed+=f[f1].ed+1;
}else if(num[u]>num[v]){
++f[f1].sid;
}else{
f[f1].fa=f2; f[f2].siz+=f[f1].siz; f[f2].ed+=f[f1].ed+1;
f[f2].sid+=f[f1].sid; --f[f2].sid;
}
}
}
for(int u : ul[k]){
int f1=find(u);
ll tmp=1ll*f[f1].ed*m1-1ll*f[f1].siz*n1+1ll*f[f1].sid*b1;
if(tmp>;maxn) { k1=k; maxn=tmp; }
}
}
PRintf("%d %lldn", k1, maxn);
return 0;
}
以上是脚本宝典为你收集整理的NOIp模拟57全部内容，希望文章能够帮你解决NOIp模拟57所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。