没进水的脑子


——博客——

noip往年题目部分思路

  • ~4.84K 字
  1. 1. 2023春季测试
    1. 1.1. T1涂色游戏
    2. 1.2. T2幂次
      1. 1.2.1. 暴力思路
      2. 1.2.2. 正解
    3. 1.3. T3圣诞树
    4. 1.4. T4 密码锁

2023春季测试

T1涂色游戏

把所有操作记录一个时间，最后输出时间最晚的那个颜色即可。

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
#include <bits/stdc++.h>
using namespace std;
int T;
int n,m,q;
const int N=1e5+10;
pair<int,int>x[N],y[N];
int main(){
	cin>>T;
	while(T--)
	{
		for(int i=1;i<=n;i++) x[i]={0,0};
		for(int i=1;i<=m;i++) y[i]={0,0};
		cin>>n>>m>>q;
		for(int i=1;i<=q;++i){
			int o,x,c;
			cin>>o>>x>>c;
			if(o==0){
				::x[x]={c,i};
			}else{
				::y[x]={c,i};
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++){
				if(x[i].second>y[j].second) cout<<x[i].first<<" ";
				else cout<<y[j].first<<" ";
			}
			cout<<endl;
		}
	}
}

T2幂次

暴力思路

枚举底数暴力判断个数。

正解

和暴力同理，加个当 时标记一下完全平方数的个数，最后统计的时候减去即可。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,bool>p;
int cnt;
int n,k;
int ping;
void work()
{
	for(int i=2;i*i*i<=n;i++)
	{
		int now=i*i,m=2;
		while(now<=n/i){
			now*=i,m++;
			if(m<k||p[now]) continue;
			if((int)sqrtl(now)*(int)sqrtl(now)==now) ping++;
			p[now]=1;
			cnt++;
		}
	}
}
signed main(){
	cin>>n>>k;
	if(k==1) {cout<<n;return 0;}
	work();
	if(k>=3) {
		cout<< cnt+1;
		return 0;
	}
	cout<<(int)sqrtl(n)+cnt-ping;
}

T3圣诞树

可以发现一个性质，就是所选路线一定不相交（题目中的例子就是来忽悠人的）。这个性质可以让我们十分方便的进行区间dp，找到最高点后枚举左右区间，记录一个dp数组 dp[i][j][1/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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int inf = 1e18;
int n;
double x[N], y[N];
struct Loc {
	int l, r, c;
	Loc(int l = 0, int r = 0, int c = 0): l(l), r(r), c(c) {}
} loc[N][N][2];
double dp[N][N][2];
double get_dis(int a, int b) {
	return sqrt(pow(x[a] - x[b], 2) + pow(y[a] - y[b], 2));
}
int check(int x) {
	if (x <= 0) x += n;
	if (x > n) x -= n;
	return x;
}
int m;
double ans=inf;
Loc Ans;
bool mn(double &x, double y) {
	if (x > y) x = y;
	return x == y;
}
void update(int l, int r) {
	if (l && mn(dp[l][r][0], dp[l - 1][r][0] + get_dis(check(m + l), check(m + l - 1)))) loc[l][r][0] = Loc(l - 1, r, 0);
	if (l && mn(dp[l][r][0], dp[l - 1][r][1] + get_dis(check(m + l), check(m - r)))) loc[l][r][0] = Loc(l - 1, r, 1);
	if (r && mn(dp[l][r][1], dp[l][r - 1][0] + get_dis(check(m - r), check(m + l)))) loc[l][r][1] = Loc(l, r - 1, 0);
	if (r && mn(dp[l][r][1], dp[l][r - 1][1] + get_dis(check(m - r), check(m - r + 1)))) loc[l][r][1] = Loc(l, r - 1, 1);
}
int st[N];
int top;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
	}
	double mx = -0x3f3f3f3f;
	for (int i = 1; i <= n; i++) if (y[i] > mx) mx = y[i], m = i;
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j][0] = dp[i][j][1] = inf;
	dp[0][0][0] = dp[0][0][1] = 0;
	for (int len = 1; len < n; len++) {
		for (int l = 0; l <= len; l++) {
			int r = len - l;
			update(l,r);
		}
	}
	cout<<m<<" ";
	for(int i=0;i<n;i++)
	for(int k=0;k<2;k++) 
	if(dp[i][n-i-1][k]<ans)
	ans=dp[i][n-i-1][k],
	Ans=Loc{i,n-i-1,k};
	while(Ans.l>0||Ans.r>0){
		st[top++]=Ans.c==0?check(m+Ans.l):check(m-Ans.r);
		Ans=loc[Ans.l][Ans.r][Ans.c];
	}
	while(top){
		top--;
		cout<<st[top]<<" ";
	}
}

T4 密码锁

+原题链接

笑死根本看不懂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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int K = 5;
int maxcnt;
int ans;
int bsmn[K], bsmx[K];
int a[N][K];
int T, k, n;
int get_val(int i) {
	int p = 0, res = 1e9;
	for (int j = 0; j < k; j++) {
		int sum = 0;
		for (int x = 0; x < k; x++) {
			sum = max(sum, max(bsmx[x], a[i][(x + j) % k]) - min(bsmn[x], a[i][(x + j) % k]));
		}
		if (sum < res) {
			p = j, res = sum;
		}
	}
	for (int j = 0; j < k; j++) {
		bsmn[j] = min(bsmn[j], a[i][(j + p) % k]);
		bsmx[j] = max(bsmx[j], a[i][(j + p) % k]);
	}
	return res;
}
int get_ans(){
	int res=0;
	for(int i=0;i<k;i++){
		res=max(bsmx[i]-bsmn[i],res);
	}
	return res;
}
mt19937 sd(chrono::_V2::steady_clock::now().time_since_epoch().count());
void work() {
	while (maxcnt--) {
		shuffle(a, a + n, sd);
		for (int i = 0; i < k; i++) bsmn[i] = bsmx[i] = a[0][i];
		for (int i = 1; i < n; i++) {
			int now=get_val(i);
			if(now>=ans) break;
		}
		int res=get_ans();
		ans=min(ans,res);
	}
	cout<<ans<<endl;
}

int main() {
	cin >> T >> k;
	while (T--) {
		cin >> n;
		for (int i = 0; i < k; i++)for (int j = 0; j < n; j++) cin >> a[j][i];
		maxcnt = 300;
		ans = 0x3f3f3f3f;
		work();
	}
}