Bzoj

题解： 参考小胖的奇偶那道题。 那道题用的并查集维护。 如果知道 i..j 之间奇偶性的话，实际上知道的是 sum[j]-sum[i-1]的奇偶性（sum为前缀和）。 ...

题解: 鉴于F[44]> 1e9。于是可以把两两乘积算出来，枚举即可。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<set> //by zrt //problem: using namespace std; int f[46]; set<int> s; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif f[0]=0;f[1]=1; for(int i=2;i<=45;i++){ f[i]=f[i-1]+f[i-2]; } int MAX=1e9; for(int i=0;i<=45;i++) s.insert(f[i]); for(int i=3;i<=45;i++){ for(int j=i;j<=45;j++){ if(f[i]*1LL*f[j]<=MAX){ s.insert(f[i]*f[j]); } } } int t,x; scanf("%d",&t); while(t--){ scanf("%d",&x); if(s.count(x)){ puts("TAK"); }else{ puts("NIE"); } } return 0; }

题解： 若d[x]<a[x]，杀这个怪是有收益的，可以按d值从小到大杀。 若d[x]>a[x]，考虑反过来的过程，如果都杀完后血量是S，那么从后向前就是 S-a[i]+d[i]，相当于第一种情况，需要按a值从大到小杀。 ...

题解： 定义F[i]为前 i-1 只奶牛工作效率的最大值。 sum[i]是Ei的前缀和。 有F[i]=max{F[j]+sum[i-1]-sum[j]} (i-j<k) 可以用单调队列维护 F[j]-sum[j] 。 ...

题解： 不能盖住好地，那么宽为1的木板只能放在行、列连通块里。 所以行、列连通块对应左、右部中的点，泥地对应边。 求二分图最小覆盖就是答案。 二分图最小点覆盖==最大匹配 ...

题解： 题意是问你一个混合图是否存在负环。 spfa即可，开始时将所有点入队，求最短路，当最短路长度超过n时，说明有负环。 code: #include<cstdio> #include<cstring> #include<algorithm> #include<queue> //by zrt //problem: using namespace std; int n,m,w; int H[505],X[6000],P[6000],E[6000]; int d[505],l[505]; int tot; inline void add(int x,int y,int z){ P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z; } int tt; queue<int> q; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif scanf("%d",&tt); while(tt--){ memset(H,0,sizeof H); tot=0; scanf("%d%d%d",&n,&m,&w); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(int i=1,x,y,z;i<=w;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,-z); } memset(d,0,sizeof d); memset(l,0,sizeof l); while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) q.push(i); bool have=0; while(!q.empty()){ int x=q.front();q.pop(); // printf("%d %d %d\n",x,d[x],l[x]); for(int i=H[x];i;i=X[i]){ if(d[P[i]]>d[x]+E[i]){ d[P[i]]=d[x]+E[i]; q.push(P[i]); l[P[i]]=l[x]+1; if(l[P[i]]>n) { have=1;goto ed; } } } } ed:; if(have) puts("YES"); else puts("NO"); } return 0; }

题目链接 题意： 给你一张n个点n-1或n条边的带权无向图。从每个点出发一直走下去，不能重复经过某个点。问走过的路径长度的数学期望是多少？ N<=100000。图中至多只有一个环，并且环长不超过20。 ...

题目链接 题意：给一张n个点，m条边的带环无向连通图，求1-n路径上的权值Xor起来的期望。 即无向有环图上求路径Xor期望。 因为是Xor操作，所以我们可以按二进制位分开考虑。 设考虑到了第k位， 那么现在这个图中的边权只有0或1。 期望问题反着设一般比较好列方程，所以我们设f[i]为从i这个点走到nXor值是1的期望，显然f[n]==0。 ∑2^k*f[1]即为答案。 设P[i]为从i点出发的走每条边的概率，应该等于1/degree[i]。 我们可以列一组dp方程： f[i]=∑P[i]*f[j](w[j,i]==0)+∑P[i]*(1-f[j])(w[j,i]==1)。 若w[j,i]==0则从这条边走过来Xor值不变，w[j,i]==1则从这条边走过来Xor值取反，(1-f[j])即为在jXor值是0的期望。 ...

题目链接 题意： 给定n,k，求 ∑(k mod i) {1<=i<=n} 其中 n,k<=10^9。 即 k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。 我们先来看商之和。 给定n,k，求∑(k/i) {1<=i<=n} 其中/为整除。 ...

题目链接 noip级数论模版题了吧。 让求三个东西： 给定y,z,p,计算Y^Z Mod P 的值。 给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数。 给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。 其中P均为素数。 来分着处理。 ...