总结

难度不算特别大，但是我是傻逼

T1 一眼贪心

T2 无脑暴力

T3 毫无头绪

T4 写不出来

（没有押好韵）

T1 地鼠游戏

题意： 有 $n$ 个物品 $a_i$,在 $t_i$ 秒之内选中 $a_i$ 个物品会获得 $v_i$ 的权值，求最大权值。

一眼贪心，跟那道 智力大冲浪 完全是一回事。把每个物品以 $v_i$ 为关键字排一遍顺序，然后枚举每一个 $a_i$ 找到一个时间点放进去，然后累加就完了。

然后我就写错了，特此贴出来警示自己。还没开 freopen(寄

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
struct ele{
	int t,v;
	double p;
}a[100005];
bool cmp(ele a,ele b){
	if(a.t==b.t) return a.v>b.v;
	return a.t<b.t;
}
int n,Time[5005],ans=0,cnt=1;
int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].t);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].v);
		a[i].p=a[i].v*1.0/a[i].t;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		if(a[i].t<cnt) continue;
		Time[cnt]=i;
		ans+=a[i].v; 
		cnt++;
	}
	printf("%d\n",ans);
	return 0;
}

鬼知道我这个贪心怎么写的

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
struct ele{
	int t,v;
	double p;
}a[100005];
bool cmp(ele a,ele b){
	return a.v>b.v;
}
int n,Time[5005],ans=0,cnt=1;
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].t);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].v),ans+=a[i].v;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		bool flg=false;
		if(!Time[a[i].t]){
			Time[a[i].t]=1;
			flg=true;
			continue;
		}
		for(int j=a[i].t;j>=1;j--){
			if(Time[j]==0){
				flg=true;
				Time[j]=1;
				break;
			}
		} 
		if(flg==false) ans-=a[i].v;
	}
	printf("%d\n",ans);
	return 0;
}

考完之后就文思泉涌两分钟就写出来了

T2 数字加密

题意： 输入一个 $n$ ,找出所有使得 $x^{2}$ 后九位等于 $n$ 的 $x$ ，且 $x,n<1e^9$ ， $x$ 的个数不超过4000

一看 $1e^9$ 就知道挨个枚举没戏，又去推了10分钟发现没什么好方法。作罢，只有打暴力，然后考虑剪个枝。

solution 1：

我在考场上写的解法，用了一点 $meet$ $in$ $middle$ 的想法，先考虑枚举前五位，将满足条件的记录下来，再拼凑后面四位 。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mul[10]={0,1,4,9,6,5,6,9,4,1},tmp=0,cnt=0,t[4005];
char n[15];
void print(int x){
	for(int i=1;i<=9;i++){
		n[i]=x%10+'0';
		x/=10;
	}
	for(int i=9;i>=1;i--) printf("%c",n[i]);
	cout<<endl;
}
int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	scanf("%s",n+1);
	for(int i=1;i<=9;i++){
		tmp=(tmp<<1)+(tmp<<3)+n[i]-'0';
	} 	
	//if(n[1]=='0'){
	//	int ans=sqrt(tmp);
	//	if(ans*ans==tmp) cout<<ans<<endl;
	//	return 0;
	//}
	for(int i=0;i<=99999;i++){
		if(mul[i%10]!=tmp%10) continue;
		ll ans=(ll)i*i%100000;
		if(ans==tmp%100000) t[++cnt]=i;
	}
	for(int i=0;i<=9999;i++){
		int k=i,x;
		for(int j=1;j<=cnt;j++){
			x=k*100000+t[j];
			ll ans=(ll)x*x%1000000000;
			if(ans==tmp) print(x);
		}
	}
	return 0;
}

看到中间注释掉的那个特判了吗？

加了特判：100->70 (悲

solution 2：

利用 $DFS$ 暴力搜索枚举每一位数字，然后写一个小剪枝：搜到第k位时，保证前k位的平方取前 $k$ 位和目标的前 $k$ 位相同即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%d", &x)
#define ll long long
int ans[4010],tot=0,key;
void dfs(int now,int k,int p){
	//now当前大小，k系数 
	if((ll)now*now % k != (ll)key % k ) return;
	if(10 == p) {
		ans[++tot] = now;return;
	}	
	for(int i=0;i<10;i++)//枚举高位 
		dfs(k*i + now ,k*10 ,p+1);			
	
}
string int2str(int s){
	string ret="";
	for(int i=1;i<=9;i++,s=s/10)
		ret= (char)(s%10+'0')+ret;
	return ret;
}
int main(){
	read(key);
	dfs(0,1,1);
	sort(ans+1,ans+tot+1); 
	for(int i=1;i<=tot;i++)
		cout<< int2str(ans[i])<<"\n";
	
	return 0;
}

solution 3:

听说还有种很玄学的做法

通过完全平方公式可以知道 $n$ 和 $1e^9-n$ 的最后几位事相同的，所以只需要枚举一半就可以了。

code：

不写了

因为过于玄学和暴力，所以说明测试数据太水了。

T3 回文子串

题意： 给出 $k$ 条变换规则，其中 $x->y$ 且 $y->x$，求一个长度为 $n$ ，每个元素不超过 $m$ 的序列最长非连续回文子串的长度。

注意：$x->y$ 且 $y->x$，然后考场上就妹啥思路了

几个数可以看作一个联通块，然后用一个区间$dp$就完事了。状态转移方程：

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int m,k,n,x,y,a[1005],fa[100005],f[1005][1005];
int find(int x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
int dfs(int l,int r){
	if(l>r) return 0;
	if(l==r) return 1;
	if(f[l][r]!=-1) return f[l][r];
	if(find(a[l])==find(a[r])) f[l][r]=max(f[l][r],dfs(l+1,r-1)+2);
	else f[l][r]=max(dfs(l,r-1),dfs(l+1,r));
	return f[l][r];
}
int main(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	memset(f,-1,sizeof(f));
	scanf("%d%d%d",&m,&k,&n);
	for(int i=1;i<=m;i++) fa[i]=i;
	for(int i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		int fx=find(x),fy=find(y);
		if(fx!=fy) fa[fx]=fy;
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	cout<<dfs(1,n);
	return 0;
}

T4 黑白图

一个 $n$ 个点 $m$ 条边构成的无向带权图。由一些黑点与白点构成。现在每个白点都要与他距离最近的黑点通过最短路连接，求这个最小代价。

很明显可以建立一个超级源点连接所有黑点，然后跑一遍最短路就可以求出到每个白点的最短路径。然后重建图跑一遍最小生成树，然后100->70。

正解应该是记录下每一个点的前驱边，将所有前驱边加在一起。

不知道为什么系统一直说我代码 $RE$ ，就先不贴代码了。