这题为啥评分"困难"?水的一批.题目描述:设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y.青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同.纬度线总长L米.现在要你求出它们跳了几次以后才会碰面.我们可以很简单的列出方程,假定跳t次会相遇.  x+m*t=y+n*t+k*l. => x+m*t=y+n*t+k*l. => (n-m)*t+k*l=(x-y).(其中t,k为未知数)这还用讲吗?就是个ex_gcd了.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long...

这题思路清晰就好了.最大公约数即为因子,我们把n的因子求出来即可,然后根据欧拉的定理即是答案了.我们知道求gcd(1a,n)=i.就等同于gcd(1a/i,n/i)=1.然后就是统计答案了.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3; ll ys[N]; inline ll get_phi(ll x)//得到x的欧拉函数. { ll cnt=x; for(ll i=2;i*i<=x;i++) { if(x%i==0) { while(x%i=...

求GCD(x,y)为素数个数也就是求d*gcd(x',y')个数,其中gcd(x',y')=1.d是质数.我们考虑枚举d.因为0<x,y<=N,那么x',y'<=N/d.题目就变简单了,那么就是枚举每个质因子.然后用前缀统计下欧拉函数. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e7+5; ll prime[N],st[N],phi[N],cnt=0,sum[N]; void get_phi(int n) { phi[1]=1; for(int ...

博弈论可以到学校好好给学弟们讲讲hh.sg函数是博弈解题的一个工具,就拿今天这个题目当例子来说吧.题目描述:给定一张NM的矩形网格纸，两名玩家轮流行动。在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。首先剪出1*1的格纸的玩家获胜。两名玩家都采取最优策略行动，求先手是否能获胜。就是这样的,怎么做呢?首先我们很容易知道(2,2),(2,3),(3,2)这三个点先手必败.然后我们根据博弈可以转化到路径的形式,sg[n][m]为0代表先手必输,对于每个点,其实都已经确定了必赢还是必输,这个题的图只有一幅,sg[x][y]=0的点一定是必输点.其他点一定是必胜点.代码...

dfs不解释. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; struct vv{ int to; double w; }; vector<vv>v[N]; double f[N]; double dfs(int x) { if(f[x]) return f[x]; int cnt=v[x].size(); for(int i=0;i<cnt;i++) { f[x]+=(v[x][i].w+dfs(v[x][i].to))/cnt; } return f[x]; } int mai...

说句实话,假如不认真再想想期望就是平均数,你会对期望很迷惑.因为dfs是从后往前的,我们要求的答案是dp[0][0][0][0][4][4]当成答案,我们考虑用后面状态来更新前面状态.对于普通的4种花色来说,假设我们现在的状态是dp[a][b][c][d][x][y].那么我们从什么转移到它呢?显然有四种: 我们令cnt=a+b+c+d+(x!=4)+(y!=4). dp[a+1][b][c][d][x][y]<-它(这样转移的概率是从最后的部分选a的概率(13-a)/(54-cnt)) dp[a][b+1][c][d][x][y]<-它(这样转移的概率是从最后的部分选b的概率(1...

大家画图自己领会,反正就是位运算. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],last[2],c1,c2,n; double ans_xor=0.0,ans_and=0.0,ans_or=0.0; void solve(int k) { c1=0,c2=0; double pos=(double)(1<<k)/n/n;//价值 last[0]=last[1]=0; for(int i=1;i<=n;i++) { int v=(a[i]>>k&amp...

这个题目和莫比乌斯反演并没有太大关系,只是用了莫比乌斯函数而已,本质就是整数分块+容斥原理.题目很简单:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d.这个怎么做呢?我们转化一下,就变成了x'=a/d,y'=b/d.并且gcd(x',y')=1的个数.这个O(n)的做法大家都会吧,但是数据自带5e5的查询,显然NT是过不去的,先讲讲nt做法,就是总数为x'*y'.x'中含有因子2的有x'/2个,同理y'中含有因子2的有y'/2.到了3也是一样的,然后我们会发现这两个的最小公倍数计算了2次,就要减去.以此容斥下去.会发现就是莫比乌斯函...

这题想清楚就不难了hh,下面讲讲思路.题目:给你n堆花的数量ai,要你从n堆花里选取m朵.问你有多少种选法?(这样当然不能重复hh).怎么想呢?假设没有我们把m朵花铺平,且加n个隔板.总方案数是多少?显然C(n+m,n).不合法的方案数是多少?这个就要用容斥原理了,C(n+m-(ai+1),n).很简单吧hhh然后我们用二进制枚举就gg了.然后由于容斥原理是有公式的,奇减偶加...emmm真的没了~代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7;...

这题就是个组合数而已hh..C(n,m)=C(n,n-m).然后就是最多sqrt(n)解决吧~还是水题舒服. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=999911659; const ll N=2e3; ll yz[N]; ll qp(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll C(ll a,ll b...

这道题怎么可能简单--acwing评分乱搞啊...首先得知道,把一个环拆成n个自环需要n-1步.然后把一个奇数环拆成两种不同的环x,y的方案数为n,把一个偶数环拆成x==y方案数为n/2,其他都是n.进一步打表可知结论,把一个大小为n的环拆成n个大小为1的自环可行种数为f[n]=n^(n-2).然后xjb可以乱搞了--好难啊.. #include <bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; const int mod=1e9+9; int a[N]; int vis[N]...

emm,线性基思想+高斯消元即可解决,其实高斯消元可以替代线性基(bolun).具体就是把你要异或的数全部进行二进制处理,假如那一位没有主元,且我这个值的最高位为1,因为每次我都会拿最高位消去其他位的1,那么我拿这个值当主元,消掉其他位子的1.emm消元完成后就是查询了,显然这个异或值可以看成一个二进制数,然后按二进制处理即可.注意处理为0的情况,假如出现为0.显然为第1小,我们k--就好,然后就没了hh.虽然我看了两天的线性基.始终没写过线性基的insert.代码如下: #include <bits/stdc++.h> using namespace std; typedef l...

这个是个很简单的水题,我就不解释了. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e4+7; ll qp(ll a,ll b)//求a^b { a%=mod; ll res=1; while(b) { if(b&1) res=(res*a)%mod; a=a*a%mod; b>>=1; } return res; } int main() { ll n,m,k,a,b; cin>>a>>b>>k>&gt...

emm这个题目说实话,假如没人指点就会很难,比如说我,,,自己看了很久没看懂,我首先读了个假题就去群里问,真tm弱智QAQ.这题假如你真懂高斯消元就会简单很多.我先带大家回顾下高斯消元..高斯消元是用来解多元一次方程组,然后可能这个方程可以用另外一个方程表示,那么我这个一次方程是不是就没有了意义?然后消完之后假如出现0!=0的方程显然无解hh..那么这个题也可以用高斯消元的思想来解,怎么解呢?我们这个题基本就变成了一个没有右边项的题目.未知数可以自己加,emm,就这样~然后讲下方程消元顺序是没关系的.且最多的装备也一定是定值,你可以类比坐标系的确定.然后消元的时候采取贪心的方式进行消元,为什么...