排位赛#13全题解！（极限在2024/10/7晚上AK我真的太高兴了哈哈哈哈哈）

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

2024-10-14 10:30:08

发布于：广东

172阅读

0回复

0点赞

个人对这些题目的感觉如下：

T1	T2	T3	T4
$\orange{签到题1}$	$\red{签到题2}$	$\orange{是我想多了TwT}$	$\color{ffe033}{大模拟}$

T5	T6	T7	T8
$\orange{小模拟}$	$\green{SA模板}$	$\green{感觉不如方格取数}$	$\green{[模板]线段树3（？}$

废话不多说开解！

T1

数据范围告诉我们需要一个O(1)的解法.
我们可以计算第一次遇到流星雨是在多少岁时，然后就能得出一生能看多少次流星雨了.

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int solve(){
	int n, m, k;
	cin >> n >> m >> k;
	k = (k + n) % 50;//计算第一次看流星雨的岁数
	m -= k; 
	if(m < 0) return 0;
	return m / 50 + 1;//得出结果
}
int main(){
	int t;
	cin >> t;
	while(t--){
		cout << solve() << endl;
	} 

	return 0;
}

T2

按题意模拟即可.

#include <iostream>
#include <cstdio>
#define F cout << "MARCO";
#define F2(s, idx) for(int i = idx; s[i] != '\0'; i++) cout << s[i];
//宏定义真的太好用了
using namespace std;
void solve(){
	string s;
	cin >> s;
	if(s[0] == 'o'){F F2(s, 1)}
	else if(s[0] == 'c' && s[1] == 'o'){F F2(s, 2)}
	else if(s[0] == 'r' && s[1] == 'c' && s[2] == 'o'){F F2(s, 3)}
	else if(s[0] == 'a' && s[1] == 'r' && s[2] == 'c' && s[3] == 'o'){F F2(s, 4)}
	else if(s[0] == 'm' && s[1] == 'a' && s[2] == 'r' && s[3] == 'c' && s[4] == 'o'){F F2(s, 5)}
	else cout << s;
	cout << endl;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

T3

贪心模拟按最远的跳

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
bool check(string &s, int n, int m){
	int idx = -1;
	while(idx + m < n){
		int i;
		for(i = m; i >= 1; i--){
			if(s[idx + i] == '#') break;//找到最远的一步能到达的方块 
		}
		if(i == 0) return 0;
		idx += i, s[idx] = '-';//跳跃，替换成空气方块 
	}
	return 1;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		int n, m;
		cin >> n >> m;
		m++;
		string s;
		cin >> s;
		if(n <= m){
			cout << "-1\n";
			continue;
		}
		int ct = 0;
		while(check(s, n, m)){
			ct++;
		}
		cout << ct << endl;
	}

	return 0;
}

T4

过程如下：
1.将输入的这组排分为顺子和非顺子两种情况去判断.
2.对于顺子，判断是否是同花顺，皇家同花顺.
3.对于非顺子，记录下相同点数的个数，按照最大值与第二大值判断属于哪种类型.

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <memory.h>
#define double pair <string, string>
using namespace std;
double a[6];
map <string, int> mp;
bool cmp(double a, double b){return mp[a.first] < mp[b.first];}
int bucket[15];
string read(){//字符串快读 
	string s;
	char c = getchar();
	while(c == ' ' || c == '\n') c = getchar();
	while(c != ' ' && c != '\n' && c != -1) s += c, c = getchar();
	return s;
}
void solve(){
	for(int i = 1; i <= 5; i++) a[i].first = read(), a[i].second = read();
	sort(a + 1, a + 6, cmp);//排序 
	int tmp = mp[a[1].first] - 1;
	bool flag = 0;
	for(int i = 2; i <= 5; i++) if(mp[a[i].first] - i != tmp) flag = 1;//是否是顺子 
	if(!flag){
		string tmp = a[1].second;
		for(int i = 2; i <= 5; i++) if(a[i].second != tmp) flag = 1;//是否是同花顺 
		puts(!flag ? a[1].first == "10" ? "Royal Flush" : "Straight Flush" : "Straight");
        return;
	}
	memset(bucket, 0, sizeof(bucket));
	for(int i = 1; i <= 5; i++) bucket[mp[a[i].first]]++;
    sort(bucket + 1, bucket + 15, greater <int>());
    int mx = bucket[1], mx2 = bucket[2];//最多和第二多的重复元素 
	puts(mx == 1 || mx == 5 ? "High Card" : mx == 4 ? "Four of a Kind" : mx == 3 ? mx2 == 2 ? "Full House" : "Three of a Kind" : mx2 == 2 ? "Two Pairs" : "One Pair");
}
int main(){
	for(int i = 2; i <= 10; i++) mp[to_string(i)] = i;
	mp["J"] = 11, mp["Q"] = 12, mp["K"] = 13, mp["A"] = 14;//将牌的点数转换为数值 
	int t;
	cin >> t;
	while(t--) solve(); 
	return 0;
}

T5

小模拟，只需要判断每次操作会不会形成新的面积为1的正方形即可.
$O(1)$ 秒了

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[1005][1005];
int n, m, k;
int x1, y1, x2, y2;
int ct[2];
bool check1(int x, int y){
	if(x == 1) return 0;
	if(!vis[x - 1][y - 1] || !vis[x - 2][y] || !vis[x - 1][y + 1]) return 0;
	return 1;
}
bool check2(int x, int y){
	if(x == n * 2 - 1) return 0;
	if(!vis[x + 1][y - 1] || !vis[x + 2][y] || !vis[x + 1][y + 1]) return 0;
	return 1;
}
bool check3(int x, int y){
	if(y == 1) return 0;
	if(!vis[x - 1][y - 1] || !vis[x][y - 2] || !vis[x + 1][y - 1]) return 0;
	return 1;
}
bool check4(int x, int y){//判断
	if(y == m * 2 - 1) return 0;
	if(!vis[x - 1][y + 1] || !vis[x][y + 2] || !vis[x + 1][y + 1]) return 0;
	return 1;
}
int main(){
	cin >> n >> m >> k;
	k *= 2;
	int cur = 1;
	while(k--){
		cur ^= 1;//交换玩家
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 == x2){
			vis[x1 * 2 - 1][min(y1, y2) * 2] = 1;//记录
			ct[cur] += check1(x1 * 2 - 1, min(y1, y2) * 2);
			ct[cur] += check2(x1 * 2 - 1, min(y1, y2) * 2);
		}else{
			vis[min(x1, x2) * 2][y1 * 2 - 1] = 1;
			ct[cur] += check3(min(x1, x2) * 2, y1 * 2 - 1);
			ct[cur] += check4(min(x1, x2) * 2, y1 * 2 - 1);
		}
	}
	cout << ct[0] << ' ' << ct[1];

	return 0;
}

T6

骗分方法显然就是求中心点（将所有横坐标纵坐标加起来除以 $n$ ），但是如何随机偏移呢？
这里就要讲到模拟退火算法了
这个算法的意思是如果新的状态的解更优，就接受新状态；否则也会以一定的概率接受这个新状态.
这个概率应为 $e^{\frac{-\Delta E}{T}}$ ，其中 $\Delta E$ 为新旧状态的能量值（就是相当于下面代码的calc函数）差， $T$ 表示当前温度（会慢慢降低，使能最终得到稳定的答案）.
~~感谢Macw让答案不需要那么准确~~
代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#define int double
#define __rand() (int(rand()) / 2147483647)
//取[0,1]间的随机数，注意评测机里rand()的最大值应为21亿
#define get(n, t) n + t * (2 * __rand() - 1)
using namespace std;
int a[10005], b[10005], c[10005];
signed n;
int mx, ansx, ansy;
int calc(int x, int y){
	int ct = 0;
	for(signed i = 1; i <= n; i++){
		int xx = a[i] - x, yy = b[i] - y;
		ct += (abs(xx) + abs(yy)) * c[i];//根据题意计算
	}
	if(ct < mx) mx = ct, ansx = x, ansy = y;//比原来解优，直接接受
	return ct;
}
void SA(){
	int t = 1e5;
	int x = ansx, y = ansy;
	while(t > 1e-15){
		int xx = get(ansx, t), yy = get(ansy, t);
		int delta = calc(xx, yy) - calc(x, y);//计算delta
		if(exp(-delta / t) > __rand()) x = xx, y = yy;//不比原来解优，以一定概率接受
		t *= 0.995;//慢慢降温
	}
}
signed main(){
	srand(time(0));
	cin >> n;
	for(signed i = 1; i <= n; i++) cin >> c[i];
	for(signed i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		ansx += a[i], ansy += b[i];
	}
	ansx /= n, ansy /= n, mx = calc(ansx, ansy);//先求中心点
	int start = clock();
	while((clock() - start) / CLOCKS_PER_SEC < 0.75) SA();//卡时，只要时间没到就一直模拟退火，使答案更精确
	printf("%.5lf", mx);

	return 0;
}

T7

不是这么大个地图我也搜不过来啊
没事遇事不决先找小数据， $M$ 这么小，有问题
我们又想到每一格的乌龟分为养或者不养两种可能（或者一种），而且不需要判断下面的格子是否有乌龟（只需满足与上面一行无乌龟相邻即可），所以可以使用状态压缩DP.
所以解法就是：枚举每一种可能，然后进行判断.
其中判断左右是否有相邻的乌龟为

!(i & (i << 1)) && !(i & (i >> 1))

判断上面是否有相邻的乌龟为

!(i & j)

判断是否有乌龟在养殖设备内为

for(int j = 0; j < m; j++){
	if(a[idx][j] == 0 && (i & (1 << j))) return 0;
}
return 1;

状态转移方程：

if(check(k, i) && !(j & k)){//满足条件
	dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod;//加上这种情况
}

注意，由于这样子可能会有一个乌龟都不放的情况，所以情况数得-1.
这样就完成了……吗？
我的方法需要枚举上下两行的状态，时间复杂度为 $O((2^M)^2)$ ，算上枚举每一行加判断是否有乌龟在养殖设备内总的时间复杂度就为 $O(NM\times2^{2M})$ ，最坏情况需要计算约 $5.2\times 10^9$ 次，根本不够用！
那怎么减小运行次数呢？
我们发现可以在判断左右是否有相邻的乌龟下手：先把满足条件的存在vector里，以后就可以通过遍历vector来减少次数了，这时计算次数就减少至约 $1.0\times 10^8$ 次了.（经测试极限数据耗时334ms）
代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int dp[505][1024];
int a[505][15];
vector <int> v;
const int mod = 1e9 + 7;
int n, m;
bool check(int i, int idx){
	for(int j = 0; j < m; j++){
		if(a[idx][j] == 0 && (i & (1 << j))) return 0;
	}
	return 1;
}
signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < (1 << m); i++){
		if(!(i & (i << 1)) && !(i & (i >> 1))) v.push_back(i);//预处理
	}
	for(int i:v){
		if(check(i, 1)) dp[1][i] = 1;//满足条件，可以放乌龟
	}
	for(int i = 2; i <= n; i++){
		for(int j:v){
			if(!check(j, i - 1)) continue;
			for(int k:v){
				if(check(k, i) && !(j & k)){//满足条件
					dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod;//加上这种情况
				}
			}
		}
	}
	int ct = 0;
	for(int i:v) ct = (ct + dp[n][i]) % mod;//加起来
	cout << ct - 1;//减去一个都不放的情况

	return 0;
}

~~如果N也小于等于10我说不定就真开搜然后做不出来摆烂了~~

T8

一眼线段树模版，但是如何求区间立方和呢？
我们先以区间平方和为例：
已知 $S_u$ 存储着 $A$ 数组区间 $[L,R]$ 的平方和，即 $S_u=\sum\limits_{i=L}^R (A_i)^2$ .
那么若想给 $[L,R]$ 中每个数都加 $x$ ，则新的 $S_u$ 为
$\sum\limits_{i=L}^R (A_i+x)^2$
$=(A_L)^2+(A_{L+1})^2+(A_{L+2})^2+...+(A_{R-1})^2+(A_R)^2+2(A_L\times x)+2(A_{L+1}\times x)+...+2(A_{R-1}\times x)+2(A_R\times x)+x^2+x^2+x^2+...+x^2$
$=S_u+2x\sum\limits_{i=L}^R 2A_i+x^2\times(R-L+1)$ .
这样就转换成区间求和的问题了！
同理可得区间立方和的求法.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005], sum[400005], sum2[400005], sum3[400005], lazytag[400005];
//sum记录区间和，sum2记录区间平方和，sum3记录区间立方和
int tmp, l, r, val, c;
const int mod = 1e9 + 7;
void update(int u, int l, int r, int val){
	if(val < 0) val += mod;
	sum3[u] = (sum3[u] + 3 * sum2[u] % mod * val % mod + 3 * sum[u] % mod * val % mod * val % mod + (r - l + 1) * val % mod * val % mod * val % mod) % mod;//a^3+3(a^2)b+3a(b^2)+b^3
	sum2[u] = (sum2[u] + 2 * sum[u] % mod * val % mod + (r - l + 1) * val % mod * val % mod) % mod;//a^2+2ab+b^2
	sum[u] = (sum[u] + val * (r - l + 1) % mod) % mod;
	lazytag[u] = (lazytag[u] + val) % mod;
}

void push_down(int u, int l, int r, int mid){
	update(u * 2, l, mid, lazytag[u]);
	update(u * 2 + 1, mid + 1, r, lazytag[u]);
	lazytag[u] = 0;
}

void __modify(int u, int l, int r, int x, int y, int val){//线段树模板
	if(x <= l && y >= r){
		update(u, l, r, val);
		return;
	}
	
	int mid = l + r >> 1;
	push_down(u, l, r, mid);
	if(x <= mid) __modify(u * 2, l, mid, x, y, val);
	if(y > mid) __modify(u * 2 + 1, mid + 1, r, x, y, val);
	sum[u] = (sum[u * 2] + sum[u * 2 + 1]) % mod;
	sum2[u] = (sum2[u * 2] + sum2[u * 2 + 1]) % mod;
	sum3[u] = (sum3[u * 2] + sum3[u * 2 + 1]) % mod;
}

int __query(int u, int l, int r, int x, int y){
	if(x <= l && y >= r) return sum3[u];
	
	int mid = l + r >> 1;
	push_down(u, l, r, mid);
	int ct = 0;
	if(x <= mid) ct += __query(u * 2, l, mid, x, y);
	if(y > mid) ct += __query(u * 2 + 1, mid + 1, r, x, y);
	return ct % mod;
}
#define modify(l, r, val) __modify(1, 1, n, l, r, val)
#define query(l, r) __query(1, 1, n, l, r)
signed main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		modify(i, i, a[i]);
	}
	while(m--){
		cin >> tmp;
		if(tmp == 1){
			cin >> l >> r >> val;
			modify(l, r, val);
		}else{
			cin >> l >> r;
			cout << query(l, r) << endl;
		}
	}

	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 9

暑假神（开学祭
其实洛谷有线段树3的，是可持久化。~~所以T8应该叫线段树2.5。~~ 贺白银！

2024-10-08 来自上海
2
- ‮队团加不）ด้้童帅_者仇复
  回复暑假神（开学祭
  是的好像是区间最值问题加可持久化
  
  2024-10-09 来自广东
  0
北辞
答案居然可以不用准确~泰6了

2024-10-09 来自广东
1
- ‮队团加不）ด้้童帅_者仇复
  回复北辞
  是的超过一半的测试点误差在1以内就能通过就很离谱
  
  2024-10-09 来自广东
  0
‮队团加不）ด้้童帅_者仇复
顶

2024-10-19 来自广东
0
cat
为什么T6会有随机数？

2024-10-12 来自广东
0
- cat
  回复cat
  难道答案是随机的
  
  2024-10-12 来自广东
  0
- ‮队团加不）ด้้童帅_者仇复
  回复cat
  搜一下模拟退火算法就知道了
  
  2024-10-12 来自广东
  0
- cat
  回复‮队团加不）ด้้童帅_者仇复
  ohohohohohohohoh
  
  2024-10-12 来自广东
  0
大吗喽
强强强

2024-10-08 来自广东
0
暑假神（开学祭
模拟退火大佬%%%

2024-10-08 来自上海
0
‮队团加不）ด้้童帅_者仇复
在25个点的作用下，我的T6代码看起来好像TLE（

2024-10-08 来自广东
0
哎嘿（军训限定
顶

2024-10-08 来自广东
0
‮队团加不）ด้้童帅_者仇复
顶

2024-10-08 来自广东
0

T1

T2

T3

T4

T5

T6

T7

T8

全部评论 9

热门讨论