101 二分答案

思路如题

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;
const int N=1e5+10;
int n;
long long k,minn,maxn;
long long  a[N];
long long ans;
int main(){
	scanf("%d%lld",&n,&k);
	minn=0x3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		minn=min(minn,a[i]);
		maxn=max(maxn,a[i]);
	}
	long long l=minn,r=minn+k;
	while(l<r){
		ans=0;
		long long  mid=(l+r+1)>>1;
		for(int i=1;i<=n;i++){
			if(mid>a[i]) ans+=mid-a[i];
		}
		if(ans>k) r=mid-1;
		else l=mid;
	}
	printf("%lld",l);
}

102 最长因子链

dp 时间复杂度$O(N^2)$

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=1e3+10;
int n;
int a[N];
int f[N];
int ans;
bool cmp(int a,int b){
	return a<b;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(!(a[j]%a[i])){
				f[j]=max(f[j],f[i]+1);
				ans=max(ans,f[j]);
			}
		}
	}
	printf("%d",ans+1);
}

103 子串的最大差

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define PII pair<int,int>

using namespace std;
const int N=5e5+10;
int n;
int a[N];
PII b[N];
long long c1[N],c2[N];
long long d1[N],d2[N];
long long  ans;
int tt;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		c2[i]=n+1;
		while(tt&&a[i]>b[tt].first){
			c2[b[tt].second]=i;
			tt--;
		}
		if(tt)c1[i]=b[tt].second;
		b[++tt]={a[i],i};
	}
	tt=0;
	for(int i=1;i<=n;i++){
		d2[i]=n+1;
		while(tt&&a[i]<b[tt].first){
			d2[b[tt].second]=i;
			tt--;
		}
		if(tt)d1[i]=b[tt].second;
		b[++tt]={a[i],i};
	}
	for(int i=1;i<=n;i++){
		ans+=((c2[i]-i)*(i-c1[i])-(d2[i]-i)*(i-d1[i]))*a[i];
	}
	printf("%lld",ans);
}

104no crossing

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=1e2+10;
int n,m,k;
int dp[N][N][N][2];
int d[N][N];
int ans;
int x,y,z;
int main(){
	memset(dp,0x3f,sizeof dp);
	memset(d,0x3f,sizeof d);
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		d[x][y]=min(z,d[x][y]);
	}
	for(int i=1;i<=n;i++){
		dp[1][0][i][1]=0;
		dp[1][i][n+1][0]=0;
	}
	for(int t=2;t<=k;t++){
		for(int i=0;i<n;i++){
			for(int j=i;j<=n+1;j++){
				for(int mid=i+1;mid<j;mid++){
					int dis=min(dp[t-1][i][j][1]+d[j][mid],dp[t-1][i][j][0]+d[i][mid]);
					dp[t][i][mid][1]=min(dp[t][i][mid][1],dis);
					dp[t][mid][j][0]=min(dp[t][mid][j][0],dis);
				}
			}
		}
	}
	ans=0x3f3f3f3f;
	for(int i=0;i<=n;i++){
		for(int j=i;j<=n+1;j++){
			ans=min(min(dp[k][i][j][0],dp[k][i][j][1]),ans);
		}
	}
	if(ans==0x3f3f3f3f) printf("-1");
	else printf("%d",ans);
}

306 树上逆序对

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#define PII pair<int,int>
using namespace std;
const int N=2e6+10;
int n,w;
long long b[N];
int ans[N];
int lowbit(int x){
	return x&(-x);
}
int query(int x){
	int res=0;
	while(x){
		res+=b[x];
		x-=lowbit(x);
	}
	return res;
}
void add(int x,int k){
	while(x<=N){
		b[x]+=k;
		x+=lowbit(x);
	}
}
priority_queue<PII,vector<PII>,greater<PII> > q;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w);
		q.push({w,i});
	}
	for(int i=1;i<=n;i++){
		PII x=q.top();
		int idx=x.second;
		q.pop();
		add(idx,1);
		for(int j=1;j<n;j++){
			long long l=j*(idx-1)+2,r=min(j*idx+1,n);
			if(l>n) break;
			ans[j]+=query(r)-query(l-1);
		}
	}
	for(int i=1;i<n;i++){
		printf("%d ",ans[i]);
	}
}

402 最大公约数

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;
const int N=2e3+10;
int n;
int a[N];
long long s[N];
long long ans[N];
map <int,int>m;
void solve(long long x){
	int b=0;
	m.clear();
	for(int i=1;i<=n;i++){
		b=max(b,++m[s[i]%x]);
	}
	ans[b]=max(ans[b],x);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	for(int i=1;i<=s[n]/i;i++){
		if(!(s[n]%i)){
			solve(i),solve(s[n]/i);
		}
	}
	for(int i=n;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);//抄抄抄，只会抄了
}

404字典序最小

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=1e6+10;
int n,m;
int a[N];
int b[N];
int c[N];
bool v[N];
int cnt;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		b[a[i]]--;
		if(v[a[i]]) continue;
		while(cnt){
			if(a[i]<c[cnt]&&b[c[cnt]]) v[c[cnt]]=0,cnt--;
			else break;
		}
		c[++cnt]=a[i];
		v[a[i]]=1;
	}
	for(int i=1;i<cnt;i++){
		cout<<c[i]<<' ';
	}
        cout<<c[cnt];
	return 0;
}

407好序列

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;
const int N=2e5+10;
int t,n;
int a[N];
int pre[N],nex[N];
map <int,int> m;
bool check(int l,int r){
	if(l>=r) return 1;
	bool f=1;
	for(int i=l;i<=((l+r)>>1);i++){
		int j=r-(i-l);
		if(pre[i]<l&&nex[i]>r) return(check(l,i-1)&&check(i+1,r));
		if(pre[j]<l&&nex[j]>r) return(check(l,j-1)&&check(j+1,r));
	}
	return 0;
}
int main(){
	scanf("%d",&t);
	while(t--){
		m.clear();
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			nex[i]=n+1;
			if(!m[a[i]]){
				pre[i]=0;
			}
			else{
				pre[i]=m[a[i]];
				nex[m[a[i]]]=i;
			}
			m[a[i]]=i;
		}
		if(check(1,n)) printf("non-boring\n");
		else printf("boring\n");
	}
}