根据题意每个数经过k次变换终会回到自身；置换的思想；离散数学里的知识；n个数可以分成m个集合，这m个集合元素的总数==n;相当于在n个数中分别选取a,b,c...个数组成m个集合；比如：假设8个数组成3个集合可以为224 （即第一个集合元素2，第二个2，第三个4）为了节省时间：每个集合大小ai可以表达为若干个质因数的h次幂形式；即从质数中选取k个按照一定的幂次，使其和等于hdp[i][j]表示前i个质数，和为j的种类数dp[i][j]+=dp[i-1][j-is_prime[i]^k]; #include<bits/stdc++.h> using namespace std; #d...

最短路，注意理解题意；只要一个戒备点次数增加，所有的戒备点次数都增加； #include<bits/stdc++.h> using namespace std; #define int long long const int inf=1e18; const int maxn=6000; int head[maxn],cnt,dis[maxn],n,m,k,a[maxn],vis[maxn]; struct edge{ int nx,to,w; }edge[maxn*maxn]; struct node{ int u,d,f;//f记录上一次戒备次数 frie...

最小生成树问题；选n-1条边； #include<bits/stdc++.h> using namespace std; //因为给边了，所以用最小生成树 const int maxn=10100; int n,m,c,sum=0,f[maxn]; struct e{ int u,v,w; }edge[2*maxn]; int find(int x) { if(x==f[x]) return x; else return f[x]=find(f[x]); } bool cmp(e i,e j) { return i.w<j.w; } void ...

#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=300000; int head[maxn],cnt,n,m,sm,f[maxn],cost=0; struct e{ int u,v,w; }edge[maxn*2]; bool cmp(e i,e j) { return i.w<j.w; } int find(int x)//并查集 { if(x==f[x]) return f[x]; else return f[x]=find...

比赛的时候感觉直接打表出矩阵会超时，就没想着打表。。。要大胆的尝试。。。先打表出矩阵（标程给出了n*M的时间复杂度，利用了筛选素数的思想），再用二维单调队列计算即可。long long开数组，内存不够。。 #include<bits/stdc++.h> using namespace std; const int maxn=5001; int a[5001][5001],n,m,h,mmax[maxn][maxn],que[maxn]; signed main() { scanf("%d %d %d",&n,&m,&h); for(int i...

标程写法：n<=2时，显然==s/2（s为叶子结点数） s>=3时，将结点按照dfs序排序，l1,l2,l3...假设s为偶数； 那么对于l1->ls/2+1, l2-> ls/2+2... 假设这条链上的儿子结点所覆盖的区间【l，r】, 如果 r < = s/2 ,那么这条边会被 lr - lr + s/2 覆盖 如果 l > s/2 ,那么这条边会被 lL-s/2 - lL; 否则，根的度数不为1，所以 l ≠ 1或者 r ≠ s 必有一个是满足的;l ≠ 1可以得出，这条边在l 1- l s/2+1; r ≠ s，这条边被 l s/2- ls 覆盖；...

把时间都转化成秒即可； #include<bits/stdc++.h> using namespace std; string a,b; int main() { cin>>a>>b; int cnt=0,sum=0; int k=((b[0]-'0')*10+(b[1]-'0'))*3600; int h=((a[0]-'0')*10+(a[1]-'0'))*3600; k+=((b[3]-'0')*10+(b[4]-'0'))*60; h+=((a[3]-'0')*10+(a[4]-'0'))*60; ...

分层图思想；一共有m条线路，则相当于m+1层；最后一层是设立虚点；每层只需与最后一层相连即可；最后一层的点相当于中转站； #include<bits/stdc++.h> #include<queue> using namespace std; const int maxn=1100; int head[maxn*maxn],cnt,m,n,dis[maxn*maxn]; struct node{ bool operator()(int x,int y){ return dis[x]>dis[y]; } }; priority_qu...

不能直接1<<j，左移会溢出。所以需要数组记录或者直接快速幂；想法比较直接，dp[j][k][2]取第j次时，到目前一共取了k次左边的，当前1为取左，0为取右；正如紫书上说的，变量有几个，设几维；（比较粗暴的方法） #include<bits/stdc++.h> using namespace std; __int128 mp[350][350],n,m,dp[350][350][2],ans; inline __int128 read(){//快读 __int128 x=0,f=1; char ch=getchar(); while(ch&lt...

#include<bits/stdc++.h> using namespace std; const int maxn=400; int head[maxn],mp[200][200],cnt,tx,ty,n,dis[maxn][maxn],vis[maxn][maxn]; int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//0==下，1==上，2==右，3==左 struct edge{ int nx,to,w; }e[6*maxn]; struct node{ int x,y,cost,dir; friend bool o...

get到了；由于每个土豆的重量都是3^（i-1），所以可以转化为二进制，对于任意一个重量二进制中都有相应的位置，第1大就是1，第二大10，第三大11...为1就加上3^(i-1) #include<bits/stdc++.h> using namespace std; #define int long long int power(int a,int b) { int ans=1; while(b) { if(b%2) ans*=a; a*=a; b>>=1; } return an...

按照列枚举，根据题意可知，每列更新过一次之后，这列就不会再更新；保证了无后效性；注意有些点是走不到的，不能用这些点更新别的点；dp[i][j]表示到达第i行第j列的金币数量 #include<bits/stdc++.h> using namespace std; const int maxn=200; int dp[maxn][maxn],mp[maxn][maxn]; int r,c; int main() { cin>>r>>c; for(int i=1;i<=r;i++) { for(int j=1;j&l...

相当于暴力吧，判断的凳子数与购物车数的大小； #include<bits/stdc++.h> using namespace std; int a[100100],b[100100],cnt; int main() { int t; cnt=0; cin>>t; while(t--) { int n,m; cnt=0; cin>>n>>m; for(int i=1;i<=n;i++) { cin&g...

找出权值最小的点，让其余的点与该点相连 #include<bits/stdc++.h> using namespace std; #define int long long const int maxn=500000; int head[maxn],f[maxn],a[maxn],cnt; signed main() { int n,min1=1e9,sum=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i],min1=min(min1,a[i]); sum+=(n-...