CSP前的板子们
Ryan_
2019-10-05 14:19:13
**矩阵乘法（矩阵快速幂）**
```
#include<cstdio>
#include<cstring>
using namespace std;
long long n,a[3],mul[3][3],res[3][3],tmp[3][3],tp[3];
void mul_1()
{
memset(tmp,0,sizeof(tmp));
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
for(register int k=1;k<=2;k+=1)
tmp[i][j]=(tmp[i][j]+res[i][k]*mul[k][j])%1000000007;
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
res[i][j]=tmp[i][j];
}
void mul_2()
{
memset(tmp,0,sizeof(tmp));
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
for(register int k=1;k<=2;k+=1)
tmp[i][j]=(tmp[i][j]+mul[i][k]*mul[k][j])%1000000007;
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
mul[i][j]=tmp[i][j];
}
void solve()
{
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
tp[i]=(tp[i]+res[i][j]*a[j])%1000000007;
printf("%lld\n",tp[1]);
}
int main()
{
scanf("%lld",&n);
if(n<=2)printf("1\n");
else
{
a[1]=a[2]=1;
for(register int i=1;i<=2;i+=1)
res[i][i]=1;
for(register int i=1;i<=2;i+=1)
for(register int j=1;j<=2;j+=1)
mul[i][j]=1;
mul[2][2]=0;
n-=2;
while(n)
{
if(n&1)mul_1();
n>>=1;
mul_2();
}
solve();
}
return 0;
}
```
```
#include<cstdio>
#include<cstring>
#define rei register int
#define ll long long
using namespace std;
const int mod = 1000;
ll n;
struct Matrix {
ll a[3][3];
} A, temp;
Matrix M_mul(Matrix x, Matrix y) {
memset(temp.a,0,sizeof(temp.a) );
for(int i=1; i<=2; ++i)
for(int j=1; j<=2; ++j)
for(int k=1; k<=2; ++k)
temp.a[i][j] = ( temp.a[i][j]%mod + (x.a[i][k]%mod)*(y.a[k][j]%mod)%mod )%mod;
return temp;
}
Matrix ksm(Matrix A, ll k) {
Matrix ans;
Matrix base = A;
memset(ans.a,0,sizeof(ans.a) );
ans.a[1][1] = ans.a[2][2] = 1;
while(k) {
if(k&1) ans = M_mul(ans,base);
base = M_mul(base,base);
k>>=1;
}
return ans;
}
int main() {
scanf("%lld",&n);
if(n&1 || n==2) return printf("0"), 0;
if(n==4) return printf("1"), 0;
n>>=1;
A.a[1][1] = 4, A.a[1][2] = -2, A.a[2][1] = 1;
Matrix ans = ksm(A,n-2);
printf("%lld",(2*ans.a[1][1]%mod +mod)%mod );
return 0;
}
```
**广搜**
```
#include<cstdio>
using namespace std;
const int MAXM = 2*1e7 +5;
const int W[5][2] = { {0,0}, {-2,1}, {-1,2}, {1,2}, {2,1} };
int n, m;
int ans;
struct node
{
int x, y;
}q[MAXM];
int head = 1, tail = 0;
void bfs()
{
while(head<=tail)
{
for(int i=1;i<=4;++i)
{
int xx = q[head].x + W[i][0], yy = q[head].y + W[i][1];
if(xx==n && yy==m) { ans++; continue; }//满足就统计
if(xx>=0 && yy<=m && xx<=n && yy>=0 )
q[++tail].x = xx, q[tail].y = yy;
}
head++;
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
q[++tail].x = 0, q[tail].y = 0;
bfs();
printf("%d",ans);
return 0;
}
```
**判断两序列的公共最长子序列**
```
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int f[N][N],a[N],b[N],n,m,cnt=0;
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0)break;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++)scanf("%d",&b[i]);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i-1]==b[j-1])f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}
printf("Twin Towers #%d\nNumber of Tiles : %d\n", ++cnt, f[n][m]);
puts("");
}
return 0;
}
```
**求与n互质的第k个正整数**
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k;
int a[N],cnt;
int main(){
cin>>n>>k;
for(int i=1;i<n;i++)
if(__gcd(i,n)==1)
a[++cnt]=i;
printf("%d",(k-1)/cnt*n+a[(k-1)%cnt+1]);
return 0;
}
```
**最小生成树prim算法**
```
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 2147483647
using namespace std;
const int N=1000005;
int nxt[N],go[N],first[N],tot,w[N],d[N],n,m,now=1,tot1,ans;
bool v[N];
void add(int x,int y,int z) {
nxt[++tot]=first[x];
first[x]=tot;
go[tot]=y;
w[tot]=z;
}
int prim() {
for(int i=first[1]; i; i=nxt[i]) {
d[go[i]]=min(d[go[i]],w[i]);
}
while(++tot1<n) {
int minn=inf;
v[now]=1;
for(int i=1; i<=n; i++) {
if(!v[i]&&minn>d[i]) {
minn=d[i];
now=i;
}
}
ans+=minn;
for(int i=first[now]; i; i=nxt[i]) {
int y=go[i];
if(d[y]>w[i]&&!v[y]) {
d[y]=w[i];
}
}
}
return ans;
}
int main() {
cin>>n>>m;
for(int i=1; i<=m; i++) {
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
for(int i=1;i<=n;i++)d[i]=inf;
//memset(v,0,sizeof(v));
d[1]=0;
printf("%d",prim());
return 0;
}
```
**对拍**
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
while(1)
{
system("rand.exe");
system("baoli.exe");
system("my.exe");
if(system("fc baoli.txt my.txt "))
while(1);
}
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------------------
#include<iostream>
#include<cstring>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
freopen("rand.txt","w",stdout);
srand(time(0));
int n;n=rand()%5+1;
cout<<n<<endl;
for(int i=1;i<=n;i++)
{
int x;x=rand()%100+2;
cout<<x<<" ";
}
return 0;
}
生成的数据
```
**求最大波形数据**
```
#include<bits/stdc++.h>
using namespace std;
int n,h[1000005],ans=1;
bool con;
int main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>h[i];
if(h[2]>=h[1]) con=1;
for(int i=1; i<=n; i++) {
if(con==0&&i==n) {
ans++;
break;
}
if(con==1) if(h[i+1]<h[i]) {
ans++;
con=0;
continue;
}
if(con==0) if(h[i+1]>h[i]) {
ans++;
con=1;
continue;
}
}
cout<<ans;
}
#include <stdio.h>
int flag = 0, now, last, n, ans = 1;
int main() {
scanf("%d%d", &n, &now);
while (--n) {
last = now;
scanf("%d", &now);
if (now == last) continue;
if (flag ^ (now < last))
ans++, flag = now < last;
}
printf("%d\n", ans);
return 0;
}
```
**最短路**
dijkstra复杂度m*log（m）/n*n
```
void dijkstra(int x){
priority_queue<int,vector<int>,less<int> >q;
memset(d,0x7f,sizeof(d));
memset(v,0,sizeof(v));
d[x]=0;
q.push(make_mair(0,x));
while(q.size()){
int x=q.top().second;q.pop();
//if(v[x])continue;
v[x]=1;
for(int i=first[x];i;i=nxt[i]){
int y=go[i],z=w[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
if(!v[y])q.push(make_pair(-d[y],y));
}
}
}
}
```
spfa复杂度km（k为较小的常数）/n*m（可用于求正负最短路，可判负环）
```
void spfa(int x) {
queue<int> q;
memset(hh,0,sizeof(hh));//判负环
memset(d,0x7f,sizeof(d));
memset(v,0,sizeof(v));
d[x]=0,v[x]=1;//入队
q.push(x);
hh[x]++;
while(q.size()) {
int x=q.top();
pop();
v[x]=0;
for(int i=first[x]; i; i=nxt[i]) {
int y=go[i],z=w[i];
if(d[y]>d[x]+z) {
d[y]=d[x]+z;
if(!v[y])q.push(y),v[y]=1;
hh[y]++;
if(hh[y]>=n)cout<<"-1",exit(0);//出现负环
}
}
}
}
```
**树的重心**
```
#include<cstdio>
#include<iostream>
#define inf 2147483647
using namespace std;
const int N=100010;
long long nxt[N<<1],go[N],tot,first[N],w[N],n,size[N],f[N];
long long min(long long a,long long b){
return a>b?b:a;
}
long long ans=inf;
void add(int x,int y) {
nxt[++tot]=first[x];
first[x]=tot;
go[tot]=y;
}
void dfs(int u,int fa,int dep) {
size[u]=w[u];
for(int i=first[u]; i; i=nxt[i]) {
if(go[i]!=fa)dfs(go[i],u,dep+1),size[u]+=size[go[i]];
}
f[1]+=w[u]*dep;
}
void dp(int u,int fa) {
for(int i=first[u]; i; i=nxt[i])
if(go[i]!=fa)
f[go[i]]=f[u]+size[1]-size[go[i]]*2,dp(go[i],u);
ans=min(ans,f[u]);
}
int main() {
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
cin>>n;
ans*=ans;
for(int i=1; i<=n; i++) {
int a,b;
cin>>w[i];
cin>>a>>b;
if(a)add(i,a),add(a,i);
if(b)add(i,b),add(b,i);
}
dfs(1,0,0);
dp(1,0);
printf("%lld",ans);
return 0;
}
-------------------------------------------
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,q;
const int N=600001;
int nxt[N],first[N],go[N],tot,size[N],f[N],ans[N],fa[N];
void add(int x,int y) {
nxt[++tot]=first[x];
first[x]=tot;
go[tot]=y;
}
void dfs(int x) {
ans[x]=x;
size[x]=1;
int maxn=0,t=0;
for(int i=first[x]; i; i=nxt[i]) {
int v=go[i];
dfs(v);
size[x]+=size[v];
if(size[v]>maxn) {
maxn=size[v];
t=v;
}
}
f[x]=maxn;
if(f[x]*2<size[x])ans[x]=x;
else {
int now=ans[t];
while(fa[now]&&(f[now],size[x]-size[now])>max(f[fa[now]],size[x]-size[fa[now]]))now=fa[now];
ans[x]=now;
}
}
int main() {
cin>>n>>q;
for(int i=2; i<=n; i++) {
int k;
cin>>k;
fa[i]=k;
add(k,i);
}
dfs(1);
for(int i=1; i<=q; i++) {
int k;
cin>>k;
cout<<ans[k]<<endl;
}
}
```
**网络流—EK算法**
```
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
const int M=200005;
int n,m,s,t;
int nxt[M],first[M],go[M],tot=1,w[M];
inline int read(){
char c=getchar();
int x=0,f=1;
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void add(int x,int y,int z){
nxt[++tot]=first[x];first[x]=tot;go[tot]=y;w[tot]=z;
}
bool inque[M];
struct node{
int v;
int edge;
}pre[M];
inline bool bfs(){
queue<int> q;
memset(inque,0,sizeof inque);
memset(pre,-1,sizeof pre);
inque[s]=1;
q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=first[u];i;i=nxt[i]){
int d=go[i];
if(!inque[d]&&w[i]){
pre[d].v=u;
pre[d].edge=i;
if(d==t)return 1;
inque[d]=1;
q.push(d);
}
}
}
return 0;
}
int EK(){
int ans=0;
while(bfs()){
int mi=inf;
for(int i=t;i!=s;i=pre[i].v){
mi=min(mi,w[pre[i].edge]);
}
for(int i=t;i!=s;i=pre[i].v){
w[pre[i].edge]-=mi;
w[pre[i].edge^1]+=mi;
}
ans+=mi;
}
return ans;
}
int main(){
register int i;
n=read();m=read();s=read();t=read();
for(i=1;i<=m;i++){
int a,b,c;
a=read();b=read();c=read();
add(a,b,c);
add(b,a,0);
}
printf("%d",EK());
return 0;
}
```
**LCIS问题**
```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=5005;
int N, M, A[MAXN], B[MAXN];
int f[MAXN][MAXN], ansj=0, lcis[MAXN][MAXN];
void LCIS();
void Input();
int main()
{
Input();
LCIS();
printf("%d\n",f[N][ansj]);
for (int p=1; p<=f[N][ansj]; p++)
printf("%d ",lcis[ansj][p]);
puts("");
return 0;
}
void LCIS()
{
memset (f, 0, sizeof(f));
memset (lcis, 0, sizeof(lcis));
for (int i=1; i<=N; i++)
{
for (int j=1,k=0; j<=M; j++)
{
if (A[i] == B[j])
{
f[i][j] = f[i-1][k]+1;
for (int p=1; p<=f[i-1][k]; p++)
lcis[j][p] = lcis[k][p];
lcis[j][f[i][j]] = A[i];
}
else f[i][j] = f[i-1][j];
if (B[j]<A[i] && f[i][j]>f[i][k])
k = j;
}
}
for (int i=1; i<=M; i++)
if (f[N][i] > f[N][ansj])
ansj = i;
return;
}
void Input()
{
scanf("%d",&N);
for(int i=1; i<=N; i++)
scanf("%d",&A[i]);
scanf("%d",&M);
for(int i=1; i<=M; i++)
scanf("%d",&B[i]);
return;
}
```
**数学方法计算第一行中间列为1的幻方**
```
#include<cstdio>
using namespace std;
int n,a[40][40],x,y;
int main(){
scanf("%d",&n);
x=1,y=(n+1)/2;
for(int i=1;i<=n*n;i++){
a[x][y]=i;
if(!a[(x-2+n)%n+1][y%n+1]) x=(x-2+n)%n+1,y=y%n+1;
else x=x%n+1;//数学运算
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}
}
```
**求数的因子较为快速的一种方法**
```
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,ans=1;
cin>>n;
int k=sqrt(n);
for(int i=2;i<=k;i++){
long long tot=1;
while(n%i==0){
n/=i;
tot++;
}
ans*=tot;
}
if(n>1)ans*=2;
cout<<ans;
return 0;
}
```
**LCS**
```
#include<bits/stdc++.h>
using namespace std;
string a,b;
int f[1001][1001];
int main() {
cin>>a>>b;
int len1=a.length();
int len2=b.length();
for(int i=1; i<=len1; i++)
for(int j=1; j<=len2; j++) {
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i-1]==b[j-1])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
cout<<f[len1][len2];
}
```
**Longest discontinuous ascending substring** 最长不连续上升子串
```
#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[1001][1001][11][2];
char s[1001],t[1001];
int main(){
int i,j,l;
cin>>n>>m>>k;
scanf("%s",s+1),scanf("%s",t+1);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(s[i]==t[j]){
for(l=1;l<=k;l++){
f[i][j][l][0]=max(f[i-1][j-1][l][0],f[i-1][j-1][l-1][1])+1;
}
}
for(l=1;l<=k;l++)f[i][j][l][1]=max(f[i-1][j][l][1],max(f[i][j-1][l][1],f[i][j][l][0]));
}
}
cout<<f[n][m][k][1]<<endl;
return 0;
}
```
**求l至r的质数个数**
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1000000;
int l , r;
int prime[maxn] , cnt , tot;
bool vis[maxn];
bool ans[maxn];
void getprime() {
for(int i = 2 ; i <= 50000 ; ++ i) {
if(!vis[i]) {
prime[++cnt] = i;
for(int j = i + i ; j <= 50000 ; j += i) {
vis[j] = 1;
}
}
}
}
long long maxnn(int a,int b) {
return a>b?a:b;
}
signed main () {
getprime();
scanf("%d%d" , & l ,& r);
for(int i = 1 ; i <= cnt ; ++ i) {
int k=maxnn(2,(l-1)/prime[i]+1);
for(int j = k* prime[i] ; j <= r ; j += prime[i])
if(j - l >= 0) ans[j - l]=1;
}
for(int i = 0 ; i <= r - l ; ++ i) if(!ans[i]) tot ++;
printf("%d\n" , tot);
return 0;
}
```
**nim游戏**
```
#include<bits/stdc++.h>
using namespace std;
long long tmp=0,n;
int t;
int main() {
cin>>t;
while(t--) {
cin>>n;
tmp=0;
for(int i=1,x; i<=n; i++)cin>>x,tmp^=x;
if(tmp)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
```