脚本宝典收集整理的这篇文章主要介绍了(联考)noip89，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
签到题
发现 (c=a-b) 不会很大，直接枚举 (c) ，一个可行的边界是 (sqrt[c]{n}) 在其附近枚举 (b) ， (a) 对应的加上 (c) 即可。
签到题。
设 (m=frac{n}{k}) 。
先判掉 (k=1) 以及无解的情况。
无解包括：(m=1,nneq1 vee n;is;even,;m;is;odd)
当 (m) 为偶数时，直接一条龙走下来。以 (n=12,k=3) 为例：
当 (m) 为奇数时，只需要让前3列相当，后 (m-3) 列可以一条龙走下来，一种可行的构造方案为，第一列从 ([1,k]) 顺着填下去，第二列填完数，将对应行的数相加排完序后能形成一个公差为1的等差数列，第三列对应填让和相等即可。 以 (n=21,k=7) 为例：
应该没出错
注意亿些细节。
30pts：暴力。
80/100pts：
先转换题意：题目实际上是让求 (x) 位置上最早 (ge y) 的时间。
于是可以直接用主席树暴力算，常数过于巨大，于是只有80pts。
对询问离线，对于修改 ([l,r]) 的操作，在 (l) 存一个 ((h,i)) ，在 (r+1) 存一个 ((-h,i)) ，并存下来每个位置对应的查询操作。
然后去扫原序列，并开一颗以询问编号为下标的树状数组，扫到点 (i) 时，先进行修改操作，如果为一个修改区间的起点，那么就会有 (h) 的贡献，为终点靠后的一个位置，则会有 (-h) 去消除前面的影响，然后查询。
查询可以通过二分树状数组解决，树状数组二分是通过 (query(mid)) 来确定上下界变化。
#include<cstdio>
#include<cctype>
#include<vector>
using std::vector;
#define re register
#define pack push_back
const int MAX = 1e6+3;
#define int long long
#define scanf oma=scanf
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,q,ans[MAX];
struct my
{ int a,b; };
vector<my>q1[MAX],q2[MAX];
#define debug(s) printf("%sn",s)
}using namespace some;
namespace Binary_Index_Tree
{
struct BIT
{
int val[MAX];
#define lowbit(x) x&-x
void modify(int x,int w)
{ for(re int i=x; i<=q; i+=lowbit(i)) { val[i] += w; } }
int query(int x,int res = 0)
{ for(re int i=x; i; i-=lowbit(i)) { res += val[i]; } return res; }
}Tree;
}using namespace Binary_Index_Tree;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("! look here,if you want to submit,please closed this");
freopen("node.in","r",stdin); //freopen("my.out","w",stdout);
#endif
freopen("concrete.in","r",stdin); freopen("concrete.out","w",stdout);
cin >> n >> q;
for(re int i=1,opt,l,r,h,x,y; i<=q; i++)
{
ans[i] = -1;
cin >> opt;
if(opt==1)
{ cin >> l >> r >> h; q1[l].pack((my){h,i}),q1[r+1].pack((my){-h,i}); }
else
{ cin >> x >> y; q2[x].pack((my){y,i}); }
}
for(re int i=1,l,r,res; i<=n; i++)
{
for(auto j : q1[i])
{ Tree.modify(j.b,j.a); }
for(auto j : q2[i])
{
l = 1,r = j.b,res = 0;
while(l<=r)
{
int mid = l+r>>1;
if(Tree.query(mid)>=j.a)
{ r = mid-1,res = mid; }
else
{ l = mid+1; }
}
ans[j.b] = res;
}
}
for(re int i=1; i<=q; i++)
{ if(ans[i]!=-1) { printf("%lldn",ans[i]); } }
//#define judge
#ifdef judge
if(system("diff my.out ans.out -w");)
{ printf("WAn"); }
else
{ printf("ACn"); }
#endif
return 0;
};
};
signed main()
{ return OMA::main(); }
((u,v)) 堵塞实际上相当于增加了点 (u) 的初始污水，减少了点 (v) 的初始污水，则 (frac{w_{old}}{deg_{u}-1}=frac{w_{new}}{deg_{u}}) , (old) 是不计堵塞， (new) 是算上堵塞的，于是 (w_{new}=frac{w_{old}cdot deg_{u}}{deg_{u}-1}) 。
那么点 (u) 初始增加的污水即为 (w_{new}-w_{old}) ，点 (v) 减少的污水即为 (frac{w_{new}}{deg_{u}}) 。记得乘上对应管道堵塞的概率。
一遍topo就可以求出每个点的期望初始污水量，带着初始值再跑一遍topo就是最后的期望排出污水量。
#include<queue>
#include<cstdio>
#include<cctype>
using std::queue;
#define re register
const int N = 2e5+3;
const int K = 5e5+3;
#define int long long
#define scanf oma=scanf
const int mod = 998244353;
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,m,r,k,inv[N];
#define debug(s) printf("%sn",s)
auto quickpow = [](int a,int b,int res = 1)
{
while(b)
{
if(b&1)
{ res = res*a%mod; }
a = a*a%mod,b >>= 1;
}
return res;
};
}using namespace some;
namespace Graph
{
int deg[N][3],du[N];
struct graph
{
int next;
int to;
int w;
}edge[K];
int cnt=1,head[N];
auto add = [](int u,int v,int w) { edge[++cnt] = (graph){head[u],v,w},head[u] = cnt; };
queue<int>q;
int val[N],delta[N];
auto topo1 = []() -> void
{
inv[0] = quickpow(inv[0],mod-2);
for(re int i=1; i<=n; i++)
{
if(!deg[i][0])
{ val[i] = delta[i] = 1; q.push(i); }
deg[i][1] = deg[i][0],inv[i] = quickpow(du[i],mod-2);
}
while(!q.empty())
{
int u = q.front(); q.pop();
int tmp = du[u]*val[u]%mod*quickpow(du[u]-1,mod-2)%mod;
for(re int i=head[u],v,w; i; i=edge[i].next)
{
v = edge[i].to,w = edge[i].w;
if(--deg[v][1]==0) { q.push(v); }
(val[v] += val[u]*inv[u]%mod) %= mod,
(delta[u] += (tmp-val[u]+mod)%mod*w%mod*inv[0]%mod) %= mod,
delta[v] = (delta[v]-tmp*inv[u]%mod*w%mod*inv[0]%mod+mod)%mod;
}
}
};
auto topo2 = []() -> void
{
for(re int i=1; i<=n; i++)
{
if(!deg[i][0])
{ q.push(i); }
deg[i][2] = deg[i][0];
//printf("%lldn",val[i]);
}
while(!q.empty())
{
int u = q.front(); q.pop();
for(re int i=head[u],v; i; i=edge[i].next)
{
v = edge[i].to;
if(--deg[v][2]==0) { q.push(v); }
(delta[v] += delta[u]*inv[u]%mod) %= mod;
}
}
for(re int i=n-r+1; i<=n; i++)
{ printf("%lld ",delta[i]); }
};
}using namespace Graph;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("! look here,if you want to submit,please closed this");
freopen("node.in","r",stdin); freopen("my.out","w",stdout);
#endif
freopen("water.in","r",stdin); freopen("water.out","w",stdout);
cin >> n >> m >> r >> k;
for(re int i=1,u,v,w; i<=k; i++)
{ cin >> u >> v >> w; add(u,v,w); deg[v][0]++,du[u]++,(inv[0] += w)%=mod; }
topo1(),topo2();
//#define judge
#ifdef judge
if(system("diff my.out ans.out -w"))
{ printf("WAn"); }
else
{ printf("ACn"); }
#endif
return 0;
};
};
signed main()
{ return OMA::main(); }
以上是脚本宝典为你收集整理的(联考)noip89全部内容，希望文章能够帮你解决(联考)noip89所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。