cgp的gcd
题目链接
思路
首先看到这题的时间限制就应该明白，直接爆力没有前途
来考虑一个问题：
如何一个数a（a$!=$1），想找到一个数和他的gcd是a，那是不是只要是a 的倍数都可以
就利用这一点，跑个筛法就好了
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
#define MAXN 100000
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
/*
1<=m<=100000
1<=a[i]<=10000
*/
int n,a[MAXN];
int ans=minn;
int main() {
cin>>n;
for(int i=1; i<=n; ++i) {
int k=read();
a[k]++;/*记录出现的次数*/
}
for(int i=2; i<=10000; ++i) { /*注意要从2开始循环，因为gcd!=1*/
int k=0;
for(int j=i; j<=10000; j+=i) { /*每次加i确保gcd始终是i*/
k+=a[j];
}
if(k>ans) {
ans=k;
}
}
cout<<ans;
return 0;
}
cgp调戏妹子
题目链接
思路
比较水的题，用拓扑排序+快速幂就行了，这里推荐一下\(lyq\)大佬的简单做法
\(lyq\)大佬已经离去....
代码
#include <iostream>
#include <cmath>
using namespace std;
int n,m,k,x,y,ok=true,next[1001];
bool check(int x) {
int i=x;
while (next[i]!=0) {
i=next[i];
if (i==x)return false;
}
return true;
}
int quick_pow_mod (int a,int b,int c) {
int s=1;
while (b) {
if (b%2) {
s%=c;
a%=c;
s*=a;
}
a%=c;
a*=a;
b=b>>1;
}
return s%c;
}
int main () {
cin>>n>>m>>k;
for (int i=0; i<m; i++) {
cin>>x>>y;
next[x]=y;
ok=check(x);
if (!ok)break;
}
if (ok)cout<<"Yes"<<endl<<k*k;
else cout<<"No"<<endl<<quick_pow_mod(2,k,9997);
return 0;
}cgp的序列
题目链接
思路
ST表的模板题目
可以看这篇博客：点这里
代码
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std;
const int maxn=50010;
const int logn=15;
int n,m,a[maxn],minn[maxn][logn+1],maxx[maxn][logn+1];
int logg[maxn],l,r,minans,maxans,ans,k;
int main()
{
//freopen("lx.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
logg[0]=-1;
for(int i=1;i<=n;i++)
{
minn[i][0]=maxx[i][0]=a[i];
logg[i]=logg[i>>1]+1;//预处理1~n对应的log
}
for(int j=1;j<=logn;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
k=logg[r-l+1];
maxans=max(maxx[l][k],maxx[r-(1<<k)+1][k]);
minans=min(minn[l][k],minn[r-(1<<k)+1][k]);
ans=maxans-minans;
printf("%d\n",ans);
}
return 0;
}cgp的背包
题目链接
思路
用3维数组f[i][j][0/1]表示放i件物品，j的题解,是否吞噬物品的最大价值
\[\begin{cases}
f[i][j][0] = f[i - 1][j - c[i]][0] + w[i]\\
f[i][j][1] = f[i - 1][j - c[i]][1] + w[i]\\
\end{cases}\]
代码
来自wxy学长
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1010,M = 13000,INF = 1e9;
ll read() {
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int g[M];
int f[N][M][2],w[M],c[M],n,m;
int main() {
n = read(),m = read();
for(int i = 1; i <= n; ++i) c[i] = read(),w[i] = read();
int P = read();
for(int i = 0; i <= m; ++i) f[0][i][1] = -INF;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= m; ++j) {
if(j >= c[i]) {
f[i][j][0] = f[i - 1][j - c[i]][0] + w[i];
f[i][j][1] = f[i - 1][j - c[i]][1] + w[i];
if(c[i] >= P) f[i][j][1] = max(f[i][j][1],f[i - 1][j][0]);
}
f[i][j][1] = max(f[i][j][1],f[i - 1][j][1]);
f[i][j][0] = max(f[i][j][0],f[i - 1][j][0]);
}
}
int ans = 0;
for(int i = 0; i <= m; ++i) ans = max(ans,f[n][i][1]);
cout<<ans;
return 0;
}