排位赛#12 T1-T5 速通

‮队团加不）ด้้童帅_者仇复

2024-09-09 21:36:15

发布于：广东

29阅读

0回复

0点赞

~~什么？没有T6？你瞅瞅哪个人能做得出来~~
感谢台风，它让我能12:00准时开赛

T1

为了计算「AI」和小林自己编写的变量的比例，可以按照以下步骤进行：

读取输入:
首先，读取整数N表示变量的数量。
然后，读取N个字符串。

接着分别判断长度是否超过 $5$ ，按题意计算出人机占的比例，秒了

//你好！我是GPT-4.0.有什么我可以帮助你的吗？
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int AIcount;
int main(){
	int times;
	cin >> times;
	int N = times;
	while(times--){
		string input_string;
		cin >> input_string;
		if(input_string.length() > 5) AIcount++;
	}
	times = N;
	cout << AIcount * 100 / times + bool(AIcount * 100 % times) << "%AI, " << 100 - AIcount * 100 / times - bool(AIcount * 100 % times) << "%Human";

	return 0;
}

当前用时:4m6s.

T2

仔细观察样例，发现大部分的结果都是 $(R_i-L_i+1)/2$ 唯一多了 $1$ 的是第一次查询，它的 $L_i$ 与 $R_i$ 均为奇数.
所以，我们得出结论:当 $L_i$ 与 $R_i$ 与 $T_i$ 的奇偶性相同时，就要加一.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100005];
int main(){
	int t;
	cin >> t;
	int n = t;
	while(t--){
		int n, m, k;
		cin >> n >> m >> k;
		n %= 2;
		cout << (k - m + 1) / 2 + (m % 2 == n && k % 2 == n) << endl;
	}

	return 0;
}

当前用时:8m16s.

T3

第一眼:01背包模板题
第二眼:？不对
这 $M$ 怎么这么逆天啊
深搜也搜不了怎么办啊
冷静，仔细看看数据范围，然后发现一个超级小的数据: $1\le v_i\le100$ .
那我们可以尝试反着dp:dp每种价值搭配的重量的最小值.
例如对于样例一，价值为 $6$ : 我们可以挑 $[1,4]$ ，也可以挑 $[2,3]$ .
我们就从这么多种搭配情况中挑重量最小的.

#include <iostream>
#include <memory.h>
using namespace std;
int w[10005], c[10005];
long long dp[100005];
int main(){
	int n, v, ct = 0;//远古模板题直接复制的 
	cin >> n >> v;
	for(int i = 1; i <= n; i++){
		cin >> w[i] >> c[i];
        ct += c[i];
	}
	memset(dp, 63, sizeof(dp));
	dp[0] = 0;
	for(int i = 1; i <= n; i++){//枚举物品 
		for(int j = ct; j >= c[i]; j--){//枚举价值 
			dp[j] = min(dp[j], dp[j - c[i]] + w[i]);
		}
	}
	for(int i = ct; i >= 0; i--){
		if(dp[i] <= v){//找最后一个重量不超过M的 
			cout << i;
			return 0;
		}
	}
}

当前用时:40m46s.
首杀+1！

T5

习惯了，看成 $1\le N,M \le3\times10^5$ 了（当时还在群里抱怨这么大个地图做个毛尬死我了
后来发现地图还挺小的，那么思路就很清晰了:
1.求出每个地区看烟花的最早时间.
2.按照题意计算.

我第一次手写了一次广搜，结果TLE了

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#define int long long
using namespace std;
struct node{
    int x, y, step;
};
vector <node> v;
int n, m, k, x, y, t;
signed dis[5005][5005];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
bool check(int x, int y){
	if(x < 1 || x > n) return 0;
	if(y < 1 || y > n) return 0;
	return 1;
}
void bfs(){
	queue <node> q;
    for(auto it:v) q.push(it);
	while(!q.empty()){
		node head = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
			if(check(xx, yy) && dis[xx][yy] > head.step + 1){
				dis[xx][yy] = head.step + 1;
				q.push({xx, yy, head.step + 1});
			}
		} 
	}
}

我发现这个模拟最坏情况时间复杂度为 $O(NMK)$ ，极限数据会耗时约21s.
没办法，只能偷学秘籍——打开Kingdom GameII，抄合理借鉴暑假神的代码.
他的代码肥肠好用，自己算了一下时间复杂度： $O(NM+K)$ ，也是非常不错好吧
然后再加上计算

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>
#pragma GCC optimize(2)
#define int long long
using namespace std;
struct node{
    int x, y, step;
    bool operator < (const node &b) const{
		return step < b.step;
	}
}a[1005];
vector <node> v;
int n, m, k, x, y, t;
signed dis[5005][5005];
bool vis[5005][5005];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
bool check(int x, int y){
	if(x < 1 || x > n) return 0;
	if(y < 1 || y > m) return 0;
	if(vis[x][y]) return 0;
	return 1;
}
void bfs(){
	queue <node> q;
	q.push(a[1]);
	dis[a[1].x][a[1].y] = a[1].step, vis[a[1].x][a[1].y] = 1;
	int ct = 2;
	while(!q.empty()){
		node head = q.front();
		q.pop();
		while(ct <= k && a[ct].step <= head.step){
			if(!vis[a[ct].x][a[ct].y]){
				dis[a[ct].x][a[ct].y] = a[ct].step, vis[a[ct].x][a[ct].y] = 1;
				q.push(a[ct]);
			}
			ct++;
		}
		for(int i = 0; i < 4; i++){
			int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
			if(check(xx, yy)){
				vis[xx][yy] = 1, dis[xx][yy] = head.step + 1;
				q.push({xx, yy, head.step + 1});
			}
		}
	}
}
const int mod = 998244353;
signed main(){
	memset(dis, 63, sizeof(dis));
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++){
        cin >> a[i].x >> a[i].y >> a[i].step;
        dis[x][y] = t;
    }
    sort(a + 1, a + k + 1);
    bfs();
    int ct = 0, pow = 1;
    for(int i = 1; i <= m; i++){
    	pow = pow * 233 % mod;
	}
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= m; j++){ 
    		pow = pow * 233 % mod;
    		ct = (ct + pow * dis[i][j] % mod) % mod;
		}
	}
	cout << ct % mod;
    
    return 0;
}

okAC了
耗时2h39m43s 首杀+2

T4

因为被弯道超车了被迫做的，本来懒得做
这道题就是找规律
这里规律就是取第二个和倒数第二个，剩下的就按照公差为 $ND$ 排

#include <iostream>
#include <algorithm>
#define print(l, r){for(int j = l; j <= r; j++) cout << m + (i + n * j - n) * k << ' '; cout << endl;}
#define int long long
using namespace std;
signed main(){
	int n, m, k;
	cin >> n >> m >> k;
	if(n < 2){
		cout << -1;
		return 0;
	}
	cout << 2 << ' ' << n * 4 + 1 << endl;
	int i = 0; print(1, 4)
	for(int i = 2; i < n; i++){print(1, 4)}
	i = 1; print(2, 5)
}