首页 > 其他分享 >2022.9.12———HZOI【CSP-S模拟4】游寄

2022.9.12———HZOI【CSP-S模拟4】游寄

时间：2022-09-22 21:11:07浏览次数：45  
标签：12 void cin re num HZOI include CSP define

\(Preface\)

\(Rank32/43\)

\(0pts + 40pts + 40pts + 20pts = 100pts\)

\[ \Huge \mathbf{水博客警告} \]

\(\mathfrak{T1}\ 石子游戏\)

\(mad\)上来一个博弈论呼我脸上，这能忍？

然后我直接跳，连交都没交

赛后贺了学长@fengwu 大佬的部分分题解，然后T掉获得\(50pts\)的好成绩

T1·50pts 
%:pragma GCC optimize(3)
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 500005
#define mod %
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
int n, can;
char vis[N];
int a[N], hav[N];
void work(){
	cin >> n;
	for (re i = 1 ; i <= n ; ++ i)
		{cin >> a[i]; vis[a[i]] = ((vis[a[i]] == true) ? (false) : (true));}
	for (re i = 1 ; i <= n ; ++ i)
		if (vis[a[i]] == true)
			hav[++ hav[0]] = a[i];
	for (re i = 1 ; i <= n ; ++ i){
		can = 0;
		for (re j = 1 ; j <= hav[0] ; ++ j)
			can ^= hav[j] mod (i+1);
		if (can == 0)
			cout << "Bob" << _;
		else 
			cout << "Alice" << _;
	}
}
#define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(stone);
    #endif
    Fastio_setup();
    work();
    return GMY;
}

\(\mathfrak{T2}\ 大鱼吃小鱼\)

根据题目模拟可以获得\(40pts\)，\(Delov\)大佬获得了\(50pts\)的高分

这题似乎挺ex的

但是有一个部分分我发现没人打，就是用桶维护的那个

然后我就去打了(赛后)，打了好长时间终于打到了\(60pts\)，码量翻倍。。。

具体而言就是维护这个数值有多少个，扔进map里(因为值域太大开数组开不下)，跳的时候直接算一个倍数然后跳就行了。

T2·60pts 
#include <iostream>
#include <set>
#include <unordered_map>
#include <cmath>
#include <unistd.h>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 300005
#define QUERY 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
	显然O(Qn)算法很好想，模拟就行了
	这题应该是O(nlogn)，然后O(1)回答询问
	从n->1倒推，似乎是个dp
	推个粑粑，这s这么大
	如果说没有修改的操作似乎是可以跑费用流的(
	不对，O(Qn)fake了，是O(Qnlogn)的
	大样例过了
	但是我知道
	会T飞的
	我来改题
	我试试把桶的那个分拿到
*/
int n, Q, opt;
long long S, K, W, final_ans, tms, target;
long long a[N];
multiset<long long> s, s2;
multiset<long long>::iterator it;
unordered_map<long long, int> mp;
unordered_map<long long, int> mp2;
/*
4
1 4 8 1
15
1 2 3
1 2 4
1 2 5
1 3 3
1 3 5
1 3 16
1 4 16
1 8 17
1 100 101
1 100 115
1 3 9
2 2
1 3 9
3 4
1 3 9
*/
void work(){
	cin >> n;
	for (re i = 1 ; i <= n ; ++ i){
		cin >> a[i];
		mp[a[i]] ++; mp2[a[i]] ++;
	}
	cin >> Q;
	if (mp.size() <= 100)
		goto Ahahahaha;
	for (re i = 1 ; i <= n ; ++ i)
		s.insert(a[i]);
	while (Q --){
		cin >> opt;
		if (opt == 1){
			cin >> S >> K;
			final_ans = 0;
			while (S < K){
				/*cerr << "集合内元素: ";
				for (it = s.begin() ; it != s.end() ; ++ it)
					cerr << *it << _;
				cerr << '\n' << '\n';*/
				it = s.lower_bound(S);
				// if (S == 2 and K == 5)
					// cerr << "debug: " << S << _ << *it << _ << *prev(it) << _ << final_ans << '\n';
				// cerr << *it << _ << *s.begin() << '\n';
				if (it == s.begin())
					{cout << "-1" << '\n'; break;}
				it = prev(it);
				S += *it; s.erase(it), s2.insert(*it);
				final_ans ++;
			}
			while (s2.empty() == false)
				s.insert(*s2.begin()), s2.erase(s2.begin());
			if (S >= K)
				cout << final_ans << '\n';
		}
		else if (opt == 2){
			cin >> W;
			s.insert(W);
		}
		else {
			cin >> W;
			it = s.lower_bound(W);
			s.erase(it);
		}
	}
	return ;
	Ahahahaha:{
		for (auto iter = mp.begin() ; iter != mp.end() ; ++ iter)
			s.insert((*iter).first);
		while (Q --){
			cin >> opt;
			if (opt == 1){
				final_ans = 0;
				cin >> S >> K;
				while (S < K){
					it = s.lower_bound(S);
					if (it == s.begin())
						{goto Breaker;}
					if (K <= *it or it == s.end())
						target = K;
					else 
						target = (*it)+1;
					tms = ceil((long double)(target - S) / *prev(it));
					it = prev(it);
					if (mp[*it] < tms){
						S += mp[*it]*(*it), final_ans += mp[*it]; mp[*it] = 0; s.erase(it), s2.insert(*it);
						while (S < target){
							it = s.lower_bound(S);
							if (it == s.begin())
								{goto Breaker;}
							it = prev(it);
							tms = ceil((long double)(target-S) / *it);
							if (mp[*it] < tms)
								{S += mp[*it]*(*it), final_ans += mp[*it]; mp[*it] = 0; s.erase(it), s2.insert(*it);}
							else if (mp[*it] == tms)
								{S += tms*(*it), final_ans += tms, mp[*it] = 0, s.erase(it), s2.insert(*it); goto Continuer;}
							else 
								{S += tms*(*it), final_ans += tms, mp[*it] -= tms; goto Continuer;}
						}
					}
					else if (mp[*it] == tms)
						{s2.insert(*it), s.erase(it), mp[*it] -= tms;}
					else 
						mp[*it] -= tms;
					S += tms * (*it); final_ans += tms;
					continue;
					Breaker:{
						cout << "-1" << '\n';
						break;
					}
					Continuer:{}
				}
				for (auto iter = mp2.begin() ; iter != mp2.end() ; ++ iter)
					mp[(*iter).first] = (*iter).second;
				while (s2.empty() == false)
					s.insert(*s2.begin()), s2.erase(s2.begin());
				if (S >= K)
					cout << final_ans << '\n';
			}
			else if (opt == 2){
				cin >> W;
				if (mp.find(W) == mp.end())
					s.insert(W);
				mp[W] ++; mp2[W] ++;
			}
			else {
				cin >> W;
				if (mp[W] == 1)
					{auto iter = s.lower_bound(W); s.erase(iter);}
				mp[W] --; mp2[W] --;
			}
		}
	}
}
#define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(fish);
    #endif
    Fastio_setup();
    work();
    return GMY;
}

\(\mathfrak{T3}\ 黑客\)

算一个上下界后直接统计就行

(年代久远思路有点忘了)

T3 
#include <iostream>
#include <cctype>
#include <cmath>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define P 1000000007
#define ll __int128
#define mod %
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
	没想到这个是签到题
	考试的时候确实有想过枚举x和y，毕竟他俩的范围这么小
	但是没往深里想
*/
inline ll read(){
	ll x = 0; char c;
	while (!isdigit(c = getchar()));
	do {x = (x << 3) + (x << 1) + (c & 15);} while(isdigit(c = getchar()));
	return x;
}
void ot(ll x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) ot(x/10);
	putchar((x%10)+48);
}
ll A, B, C, D, dw1, dw2, up1, up2, final_ans;
inline ll gcd(ll x, ll y){return ((y == 0) ? (x) : (gcd(y, x%y)));}
void work(){
	A = read(), B = read(), C = read(), D = read();
	for (ll x = 1 ; x <= 999 ; ++ x){
		for (ll y = 1 ; y <= 999-x ; ++ y){// 限制max{x+y} = 999(
			if (gcd(x, y) == 1){// 无法再约分
				// x*k / y*k = x/y，这样才能约掉同样的倍数然后成功配对dsu(
				dw1 = ceil((1.0 * A) / x), up1 = B / x;// 有up1-dw2个数是x倍数
				dw2 = ceil((1.0 * C) / y), up2 = D / y;
				dw1 = MAX(dw1, dw2), up1 = MIN(up1, up2);
				if (dw1 <= up1){
					final_ans += (up1-dw1+1) * (x+y) mod P;
					if (final_ans >= P)
						final_ans -= P;
				}
				// ot(dw1), putchar(' '), ot(up1), putchar(' '), ot(dw2), putchar(' '), ot(up2), putchar('\n');
			}
		}
	}
	ot(final_ans), putchar('\n');
}
#define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(hacker);
    #endif
    // Fastio_setup();
    work();
    return GMY;
}

\(\mathfrak{T4}\ 黑客(续)\)

丧心病狂考高精

而且贺了衣服的题解

T4 
#include <iostream>
#include <cstdio>
#include <cstring>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 505
#define M 105
#define KKK 15
#define SSS 1032
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
	贺衣服的题解 
*/
struct Int{
	long long num[85];
	Int(){num[0] = 1;}
	const long long len = 100000000000000000;
	void init(){memset(num, 0, sizeof(num)); num[0] = 1;}
	Int operator +(const Int &b) const{
		Int c;
		c.init(); c.num[0] = MAX(num[0], b.num[0]);
		for (re i = 1 ; i  <= c.num[0] ; ++ i){
			c.num[i] += num[i] + b.num[i];
			if (c.num[i] >= len){
				c.num[i] -= len;
				c.num[i+1] ++;
			}
		}
		if (c.num[c.num[0]+1] > 0)
			c.num[0] ++;
		return c;
	}
	Int operator *(int b) const{
		Int c;
		c.init(); c.num[0] = num[0] + 1;
		for (re i = 1 ; i <= c.num[0] ; ++ i){
			c.num[i] += num[i] * b;
			c.num[i+1] += c.num[i] / len;
			c.num[i] %= len;
		}
		while (c.num[c.num[0]] == 0 and c.num[0] > 1)
			c.num[0] --;
		return c;
	}
	void operator +=(const Int &b){
		num[0] = MAX(num[0], b.num[0]);
		for (re i = 1 ; i <= num[0] ; ++ i){
			num[i] += b.num[i];
			if (num[i] >= len)
				num[i] -= len, num[i+1] ++;
		}
		if (num[num[0]+1] > 0)
			num[0] ++;
	}
	void operator *=(int b){
		num[0] ++;
		for (re i = 1 ; i <= num[0] ; ++ i){
			num[i] += num[i] * (b-1);
			num[i+1] += num[i] / len;
			num[i] %= len;
		}
		while (num[num[0]] == 0 and num[0] > 1)
			num[0] --;
	}
	void output(){
		printf("%lld", num[num[0]]);
		for (re i = num[0]-1 ; i >= 1 ; -- i)
			printf("%017lld", num[i]);
	}
};
int n, m, K, S, p;
Int final_ans1, final_ans2;
char no[KKK][KKK], can[SSS][KKK];
Int f[3][SSS], sum[3][SSS];
void work(){
    scanf("%d%d%d", &n, &m, &K); S = (1 << K) - 1;
    for (re i = 1, x, y ; i <= m ; ++ i)
    	{scanf("%d%d", &x, &y); no[y][x] = true;}
    for (re i = 0 ; i <= S ; ++ i){
    	for (re j = 1 ; j <= K ; ++ j){
    		char cant = false;
    		for (re k = 1 ; k <= K ; ++ k){
    			if (((i >> (k-1)) & 1) == 0)
    				continue;
    			if (no[j][k] == true)
    				{cant = true; break;}
			}
			if (cant == false)
				can[i][j] = true;
		}
	}
	f[p][0].num[1] = 1;
	for (re i = 1 ; i <= n ; ++ i){
		p ^= 1;
		for (re j = 0 ; j <= S ; ++ j)
			f[p][j].init(), sum[p][j].init();
		for (re j = 0 ; j <= S ; ++ j){
			for (re k = 1 ; k <= K ; ++ k){
				if (can[j][k] == false)
					continue;
				int nxts = j | (1 << (k-1));
				f[p][nxts] += f[p^1][j];
				sum[p][nxts] += sum[p^1][j] * 10;
				sum[p][nxts] += f[p^1][j] * k;
			}
		}
	}
	final_ans1.init(), final_ans2.init();
	for (re i = 0 ; i <= S ; ++ i)
		final_ans1 += f[p][i], final_ans2 += sum[p][i];
	final_ans1.output(), putchar('\n');
	final_ans2.output(), putchar('\n');
}
#define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(hacker2);
    #endif
    // Fastio_setup();
    work();
    return GMY;
}

标签：12,void,cin,re,num,HZOI,include,CSP,define
From： https://www.cnblogs.com/charphi/p/16720764.html

相关文章

  • 将{"123","456"}集合转化为('123','456')
    需求分析优化接口时,需要手动拼接sql去调取神策的接口获取数据。好比将List<String>={"123","456"}集合转化为('123','456')。1publicclasstest3{23p......
  • CSP 202104_2
    CSP202104_2目录CSP202104_2题目思路Code题目邻域均值思路CSP一贯风格，纯暴力一眼可见的70pts二维前缀和，没什么要说的Code#include<bits/stdc++.h>usingnamespac......
  • CSP-S模拟8
    不愧为\(IOI\)赛制A.选举以为是个贪心题，结果怎么贪都不对，到九点多意识到这是\(DP\)，然后就不想打了。。。。写了个假\(DP\)，就不在这里说了。。首先如果我们知道......
  • CSP - S 模拟9
    CSP-S模拟9赛时T2想了两个小时无果，极限一小时写T3险些模拟退役，最后3分钟调出来T3AARC125C考场上打表找规律我们先把\(k\)个数放好，考虑一个一个贪心插入。每回......
  • P3530 [POI2012]FES-Festival
    传送门思路对于第一种限制，我们连接\((x,y)=1\)，\((y,x)=-1\)对于第二种限制，我们连接\((x,y)=0\)如果一个图只有第一种边，那么要么就是没有解（有环），要么答案就是点的个数......
  • VS2012使用nuget时提示”基础连接已关闭“基础连接已经关闭: 未能为 SSL/TLS 安全通道
    上手运维着几个老系统，需要使用VS2012，最近使用NUGET的时候，总是提示“基础连接已经关闭:未能为SSL/TLS安全通道建立信任关系”，网上找了好久，基本上都是说修改注册表就可以，......
  • 类欧几里得，以及ARC111E和ARC123E
    例题https://atcoder.jp/contests/practice2/tasks/practice2_c在\(O(\log(n+m+k+b))\)的时间复杂度求：\[\sum_{i=0}^{n-1}\lfloor{\frac{ki+b}{m}}\rfloor\]其中\(n,......
  • CSP-S模拟8
    Cat最喜欢清北营赛制了！但是这个赛制暗示了以下全是鬼畜题…… A.选举居然可以dp，我本来以为是贪心的题，联想到了学长提到的过关得到相应的星星，可以选择拿1颗或两颗，代价......
  • 1216. 饮料换购
    https://www.acwing.com/problem/content/1218/大水题233简单数理分析即可知由n瓶饮料,可以产生n个瓶盖,又可以用n个瓶盖换取n/3(下取整)瓶饮料,如此反复换取,直至瓶......
  • webpack基础_12开发服务器&自动化
    开发服务器&自动化每次写完代码都需要手动输入npxwebpack指令才能编译代码，太麻烦了，我们希望一切自动化。1.下载包npmiwebpack-dev-server-D2.配置webpack.confi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99