大工之星编程挑战赛第一周题解

去年出了一车BUG，今年希望举办的时候希望没有BUG。最后看来，榜看起来还是很好看的，没有人AK，前排过的很多，后排也有题过。榜单也没有出现断层，算是成功了。
其实出了一点小锅，幸亏问题不大（逃）
ileln眼中的题目难度：
A 题解 A.猛犸不上班

本场最签到的题。输出3即可。题面是整蛊的。

#include
using namespace std;
int main() {
	cout<<3< 
B.ileln的海鲜大餐 
签到题，把所有数加起来就行了。
 
#include
using namespace std;
#define N 1000005
int a[N],n; 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0;
	for(int i=1;i<=n;i++) ans+=a[i];
	cout< 
C.左特买镜子 
D.ileln想大吃一顿 
基础背包问题，记三维i,j,k，
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        [
       
       
        k
       
       
        ]
       
      
      
       dp[i][j][k]
      
     
    dp[i][j][k]表示前i个食物，j长胖量，k含猪量的最大快乐值,食物含猪量范围是烟雾弹，大家不用关心。
 
更新即为：
 
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         [
        
        
         j
        
        
         ]
        
        
         [
        
        
         k
        
        
         ]
        
        
         =
        
        
         m
        
        
         a
        
        
         x
        
        
         (
        
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         −
        
        
         1
        
        
         ]
        
        
         [
        
        
         j
        
        
         ]
        
        
         [
        
        
         k
        
        
         ]
        
        
         ,
        
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         −
        
        
         1
        
        
         ]
        
        
         [
        
        
         j
        
        
         −
        
        
         w
        
        
         [
        
        
         i
        
        
         ]
        
        
         ]
        
        
         [
        
        
         k
        
        
         −
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         ]
        
        
         )
        
       
       
         dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-p[i]]) 
       
      
     dp[i][j][k]=max(dp[i−1][j][k],dp[i−1][j−w[i]][k−p[i]])
 最后统计第n位所有dp值的最大值即可。
 
注意更新时的背包预处理操作
 
#include
using namespace std;
#define ll long long
#define N 2005 
int n,K,P;
ll dp[N][N][11];
ll w[N],v[N],p[N];
int main(){
	cin>>n>>K>>P;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i],&v[i],&p[i]);
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int j=0;j<=K;j++){
			for(int k=0;k<=P;k++){
				dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
				dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
			}
		}
		for(int j=w[i];j<=K;j++){
			for(int k=p[i];k<=P;k++){
				dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
				dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-w[i]][k-p[i]]+v[i]);
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=K;i++){
		for(int j=0;j<=P;j++){
			ans=max(ans,dp[n][i][j]);
		}
	}
	cout< 
E.左特照镜子 
F.查字典-简单版 
G.查字典-困难版 
H.ileln的大工食堂化计画 
签到题，只需要看看相邻食堂之间的差值需要多少天来全部占领就行。
 小心，你的学校可能没有食堂
 
#include
using namespace std;
#define N 1000005
int n,m;
int cnt=0;
int p[N],a[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		if(a[i]==1){
			p[++cnt]=i;
		}
	}
	if(!cnt){
		cout<<-1;return 0;
	}
	int ans=max(p[1]-1,n-p[cnt]);
	for(int i=2;i<=n;i++){
		int val=p[i]-p[i-1]-1;
		if(val&1) val++;
		val/=2;
		ans=max(ans,val);
	}cout< 
I.比赛前夜 
J.ileln的牛奶巧克力威化小饼干 
线段树，对于一个区间有没有相同元素这样的问题，考虑预处理，to[i]表示下一个与i位置值相同的位置，对区间to数组求最小值，假如没有超过区间右端点，就是有相同元素，否则没有
 修改的话其实考虑把所有相同的数维护成一个链表就好了，删掉一个数就相当于删掉链表的一个节点
 to数组只需正着扫一遍即可
 注意先区间离散化！当然stl::map也可以
 
#include
using namespace std;
int n,q;
int a[500005];
struct ee{
	int id,a,b;
};ee w[500005];
struct tree{
	int to;
};tree t[2000005];
int head[1000005],from[500005],to[500005];
int cmt=0,cc=0;
int ans;
bool cmp1(ee a,ee b){
	return a.aqr) return;
	if(l==r){
		if(l==ql){
			to[ql]=to[to[ql]];
			t[v].to=to[ql];
		}
		return;
	}
	int mid=(l+r)/2;
	del1(l,mid,2*v,ql,qr);
	del1(mid+1,r,2*v+1,ql,qr);
	t[v].to=min(t[2*v].to,t[2*v+1].to);
}
void del2(int l,int r,int v,int ql,int qr){
	if(rqr) return;
	if(l==r){
		if(l==ql) t[v].to=1000000;
		return;
	}
	int mid=(l+r)/2;
	del2(l,mid,2*v,ql,qr);
	del2(mid+1,r,2*v+1,ql,qr);
	t[v].to=min(t[2*v].to,t[2*v+1].to);
}
void query(int l,int r,int v,int ql,int qr){
	if(rqr) return;
	int mid=(l+r)/2;
	if(ql<=l&&r<=qr){
		ans=min(t[v].to,ans);
		return;
	}
	query(l,mid,2*v,ql,qr);
	query(mid+1,r,2*v+1,ql,qr);
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		from[i]=0;
		to[i]=1000000;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i].a);
		w[i].id=i;
	}
	sort(w+1,w+n+1,cmp1);
	for(int i=1;i<=n;i++){
		if(w[i].a!=w[i-1].a) w[i].b=++cc;
		else w[i].b=cc;
	}
	sort(w+1,w+n+1,cmp2);
	for(int i=1;i<=n;i++) a[i]=w[i].b;
	for(int i=1;i<=n;i++){
		if(head[a[i]]){
			to[head[a[i]]]=i;
			from[i]=head[a[i]];
		}
		head[a[i]]=i;
	}
	build(1,n,1);
	for(int i=1;i<=q;i++){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int x;
			scanf("%d",&x);
			if(from[x]){
				del1(1,n,1,from[x],from[x]);
			}
			if(to[x]!=1000000) from[to[x]]=from[x];
			del2(1,n,1,x,x);
		}
		else{
			int l,r;
			scanf("%d%d",&l,&r);
			ans=1000000;
			query(1,n,1,l,r);
			if(ans<=r) printf("NOn");
			else printf("YESn");
		}
	}
}
 
K.左特想自习