11.13 模拟赛小记

30+0+10+0

全真模拟。今天的模拟赛有一种格外的说不上来的绝望的感觉。很不好描述的。一直在想如果这是真实的 noip 赛场那我不就大寄特寄了。

下午因为不舒服所以玩了一下午（？）一直在机惨别人（？）玩的很开心。

但还是想看大家在机房跳钢管舞喵（？

A.game

赛时看到这个题之后就变得很愚蠢。写了奇怪的桶 + 暴力背包，调了两个小时，最后获得了 30pts 的好成绩。是谁破防了我不说。

正解是，背包。倒着这样跑回跳过许多无用的数。在洛谷上可以跑过，oj 的机子需要火车头或者数组随机排序。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const int M=1e3+10;
int n,m;
int s1,s2;
int vis1[N],vis2[N];
ll w1[M],v1[M],w2[M],v2[M];
ll f[N],g[N]; 
ll ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&w1[i],&v1[i]);
		s1+=w1[i];
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&w2[i],&v2[i]);
		s2+=w2[i];
	}
	memset(f,-0x3f,sizeof f);
	memset(g,-0x3f,sizeof g);
	vis1[0]=1,vis2[0]=1;
	g[0]=f[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=s1;j>=w1[i];j--)
			if(vis1[j-w1[i]]){
				f[j]=max(f[j],f[j-w1[i]]+v1[i]);
				vis1[j]=1;
			}
	for(int i=1;i<=m;i++)
		for(int j=s2;j>=w2[i];j--)
			if(vis2[j-w2[i]]){
				g[j]=max(g[j],g[j-w2[i]]+v2[i]);
				vis2[j]=1;
			}
	for(int i=1;i<=min(s1,s2);i++)
		if(vis1[i]&&vis2[i]) ans=max(ans,f[i]+g[i]);
	printf("%lld",ans);
}

B.dig

这是 20pts 的暴力凑点字数。赛时最后 2h 大脑再次宕机无法思考，没考虑到序列有负数嗯...

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52;
int T;
int n;
int a[N][N];
void solve(){
	int k;
	scanf("%lld%lld",&n,&k);
	int s1=0,s2=0;
	int ans1=0,ans2=0;
	a[1][1]=0;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			scanf("%lld",&a[i][j]);
		}
		s1+=a[i][1];
		s2+=a[i][i];
		ans1=max(ans1,s1);
		ans2=max(ans2,s2);
	}
	printf("%lld\n",ans1+ans2);
}
signed main(){
	scanf("%lld",&T);
	while(T--) solve();
}

C 大模拟。

D 不会