DATE #:202409015
ITEM #:DOC
WEEK #:SUNDAY
DAIL #:捌月拾叁
TAGS
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1863449738&auto=0&height=66" width="330"></iframe> < BGM = "阿尔茨海默症 - 盼钰" > < theme = oi-contest > < [NULL] > < [空] > < [空] >鱼不畏水 鸟不惧高 猫不怕鱼 你不爱我
A. 夕景昨日
时间限制: 1 s 内存限制: 500 MB 测评类型: 传统型
题目描述
\(\text{Shintaro}\) 制作了 \(n\) 个开关，每个开关的状态可被设置为 \(+\) 或 \(-\)。
现在你有一个数列 \(A=(a_1,⋯,a_n)\) ，和一个初始值为 \(0\) 的变量 \(v\) 。你可以自由地操纵开关，当第 \(i\) 个开关被设置为 \(+\) 状态时， \(v\) 会加上 \(a_i\) ，被设置为 \(-\) 状态时， \(v\) 会减去 \(a_i\)。
请你判断是否有两种及以上不同的方式操纵开关，使得最后得到的 \(v\) 值相等。
输入格式
第一行一个数 \(n\)，表示开关的个数
第二行 \(n\) 个数，第 \(i\) 个数表示 \(a_i\)
输出格式
如果有请输出
Yes，否则输出No。样例输入
2 3 1 2 3 4 3 4 5 10样例输出
Yes No样例说明
对于第一组数据：
\(+1+2-3=0\)
\(-1-2+3=0\)
数据范围
- 对于 \(20\%\) 的数据，\(n≤10\)；
- 对于 \(50\%\) 的数据，\(n≤1000\)；
- 对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(0≤a_i≤500000\)，\(1\le T\le 10\)。
//2024.9.15
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr itn oo = 100005;
int t,n;int st[oo];
unordered_map<int,itn> vis;
itn ned[oo],cnt;
main(void){
//fre();
cin.tie(0)->sync_with_stdio(0);
cin >> t;while (t--){
vis.clear();cnt = 1;vis[0] = 1;
cin >> n;for(itn i=1;i<=n;i++)cin >> st[i];
sort(st+1,st+n+1);bool flag = 0;
for (itn i=1;i<=n;i++){
if (vis[st[i]]){cout<<"Yes"<<'\n';flag=1;break;}
int top = cnt;
for(itn j=1;j<=cnt;j++){
itn p = ned[j]+st[i];
//p_(true,vis[p],i,j);
if (vis[p]) continue;
vis[p] = 1;ned[++top] = p;
}
cnt = top;
}
if (!flag)cout << "No" << '\n';
}
exit(0);
}
首先注意到数字个数超过 \(20\) 就一定是 Yes。假如我们把能得到的 \(v\) 值记录在 vis 数组里，那么加入一个数相当于把当前的 vis 数组里的数左右平移，并删除原来的数。因为 vis 数组一旦出现重复的数字就是 Yes，所以 vis 数组大小每次都会乘以 2。那么为 No 的范围显然是 \(\log W\)。极限构造可以考虑 \(1\ 2\ 4\ 8\ \dots\)
剩下的部分可以使用 \(2^n\) 暴力。
B. 透明答案
时间限制: 1 s 内存限制: 512 MB 测评类型: 传统型
题目背景
你听说过 Anti-Nim 博弈吗？Anti-Nim 博弈是 Nim 博弈的变形，它的基本玩法是两人轮流取石子，把物品全部取完者失败。它是一个古老的博弈游戏，也是 czy 数学领域的一个经典问题。而今天我们要讲述的问题，就和 Anti-Nim 博弈没有丝毫的关系。
题目描述
Acestar 和 Blueqwq 在玩简单的取石子游戏。最初有 \(n\) 堆石子，每堆有 \(2\) 块。
Acestar 和 Blueqwq 轮流取石子（从 Acestar 开始）。每一次取石子时当前玩家可以任选一堆，如果还剩下 k\(k\) 块石子，则可以从这堆中取出 \(1\) 到 \(k\) 之间的任意数量的石子。
此外，每 \(3\) 回合他们会添加一堆 \(2\) 块的石子。换句话说，在第 \(t\) 次操作（两个人操作的总次数）之后，如果 \(t\) 可以被 \(3\) 整除，则添加一堆 \(2\) 块石子的石子堆。
（即使在第 \(t\) 次操作中取完了所有石子，如果 \(t\) 可被 \(3\) 整除，也会添加新石子堆并继续游戏。）
双方都采取最优策略，无法操作的玩家输掉游戏。请你判断哪个玩家获胜。
输入格式
第一行一个数 \(T\)，表示数据组数。
接下来 \(T\) 行，每行一个数 \(n\)，表示最初石子的堆数。
输出格式
对于每组数据，如果 Acestar 获胜则输出
Acestar，否则输出Blueqwq。样例输入
2 1 998样例输出
Acestar Blueqwq数据范围
- 对于 \(30\%\) 的数据，\(n≤10\)；
- 对于 \(100\%\) 的数据，\(n≤1000\)，\(1\le T\le 10\)。
//2024.9.15
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long
#define itn long long
int t,n;
main(void){
//fre();
cin.tie(nullptr)->ios::sync_with_stdio(false);
cin >> t;while(t--){
cin >> n;
cout << (n%3==2?"Blueqwq":"Acestar") << '\n';
}
exit(0);
}
wtm推了得有一个小时sg函数的，然后是sima结论题
C. 界外科学
时间限制: 1 s 内存限制: 500 MB 测评类型: 传统型
题目描述
\(\text{ENE}\) 是一位电脑少女，这天她在帮 \(\text{Shintaro}\) 网上购物。网店一共有 \(n\) 件物品，第 \(i\) 件物品有 \(a_i\) 的价格，并且购买这件物品会给 \(\text{Shintaro}\) 带来 \(b_i\) 的满足度，不同的物品获得的满足度会累加。
\(\text{Shintaro}\) 最多只能支付 m\(m\) 元。由于他资金有限，ENE\(\text{ENE}\) 黑入了网店的支付系统。在她操作之后，总价格的计算方式是将所有物品的价格给 \(\text{xor}\) （异或运算）起来。
如 \(\text{Shintaro}\) 现在买了价格为 \(1\) 、\(2\) 、\(4\) 、\(7\) 的四件物品，总价格为\(1\oplus 2\oplus 4 \oplus 7=0\)。
\(\text{Shintaro}\) 现在想知道在足够支付所买的物品的前提下，他最多能获得多少满足度。
输入格式
第一行两个数 \(n,m\) ，表示物品的个数和 \(\text{Shintaro}\) 最多能支付多少钱。
第二行 \(n\) 个数，第 \(i\) 个数 \(a_i\) 表示第 i\(i\) 件物品的价格。
第三行 \(n\) 个数，第 \(i\) 个数 \(b_i\) 表示第 i\(i\) 件物品能带给 \(\text{Shintaro}\) 的满足度。
输出格式
一行一个数表示答案。
样例输入1
4 3 1 3 4 5 2 5 -3 100样例输出1
104样例输入2
1 1000000000 1 -1000000000样例输出2
0样例输入3
4 8 1 2 4 8 13 6 32 50样例输出3
51样例1说明
购买全部 \(4\) 件物品，总花费为 \(1⊕3⊕4⊕5=3\)，总价值为 \(2+5-3+100=104\)。
数据范围
- 对于 \(30\%\) 的数据，\(n≤5\)；
- 对于 \(50\%\) 的数据，\(n≤20\)；
- 对于另外 \(20\%\) 的数据，\(1≤m,a_i≤100\)；
- 对于 \(100\%\) 的数据，\(1≤n≤36\)，\(1≤m,a_i,|b_i|≤10^9\)。有 \(70\%\) 数据随机。
你猜为什么随机：
//2024.9.15
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo=40;
constexpr itn op=1<<18;
constexpr itn of=30;
constexpr int inf=1e18;
int n,n1,n2;
int m,a[oo],b[oo];
struct trie{
int son[of*op][2];
int mx[op*oo];
int cnt;
trie() : cnt(1){mx[0]=mx[1]=-inf;}
void ins(int x,int val){
int p=1;
for(int i=of-1;i>=0;i--){
int c=x>>i & 1;
if(!son[p][c]) mx[son[p][c]=++cnt]=-inf;
p=son[p][c];
mx[p]=max(mx[p],val);
}
}
int qry(int x){
int p=1;
int ans=-inf;
for(int i=of-1;i>=0&&p;i--){
int c=m>>i & 1;
if(m>>i & 1){
ans=max(ans,mx[son[p][x>>i & 1]]);
p=son[p][!(x>>i & 1)];
}
else p=son[p][x>>i & 1];
}
return ans;
}
}t;
main(void){
//fre();
cin.tie(0)->ios::sync_with_stdio(false);
cin>>n>>m;m ++;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
n1=n/2;
int opt=0,ed=n1;
int ans=-inf;
function<void(int,int,int)>dfs=[&](int cur,int xr,int sum){
if(cur == ed+1){
if(!opt) t.ins(xr,sum);
else ans=max(ans,t.qry(xr)+sum);
return ;
}
dfs(cur+1,xr,sum);
dfs(cur+1,xr^a[cur],sum+b[cur]);
};
dfs(1,0,0); opt=1,ed=n;
dfs(n1+1,0,0);
cout << ans << '\n';
exit (0);
}
折半搜索，然后好像就不用讲了。。。。
D. 回忆补时
时间限制: 1 s 内存限制: 500 MB 测评类型: 传统型
题目描述
\(\text{Shintaro}\) 有 \(n\) 条直线，第 \(i\) 条直线 \(l_i\) 可以被描述为 \(k_ix+b_i\)。
这天 \(\text{Ayano}\) 和 Shintaro\(\text{Shintaro}\) 在一起玩游戏。每局游戏 \(\text{Ayano}\) 会给出一个整数 \(x\)，然后让 \(\text{Shintaro}\) 选两条不同的直线 \(l_i,l_j\)，得到 \(y=k_j\times (k_i\times x+ b_i)+b_j\) 作为他的得分。
作为游戏中级高手，\(\text{Shintaro}\) 觉得得分肯定是越大越好，然而他不知道自己的得分是否达到了最大。所以对于每局游戏里 \(\text{Ayano}\) 给出的整数 \(x\) ，请你告诉 \(\text{Shintaro}\) 可能得分的最大值。
输入格式
第一行一个数\(n\)，表示直线的条数。
接下来 \(n\) 行，其中第 \(i\) 行两个数 \(k_i,b_i\) 用于描述第 \(i\) 条直线。
接下来一行一个数 \(q\)，表示游戏次数。
接下来 \(q\) 行，其中第 \(i\) 行一个数 \(x_i\) 表示第 \(i\) 局游戏里 \(\text{Ayano}\) 给出的整数。
输出格式
共 \(q\) 行，第 \(i\) 行输出一个整数表示第 \(i\) 局游戏的可能得分的最大值。
样例输入
4 -2 3 4 7 5 8 1 20 3 0 10 -10样例输出
108 243 123数据范围
\(30\%\)：\(n,q≤100\)
\(60\%\)：\(n,q≤3000\)
\(100\%\)：\(2≤n,q≤100000,~|x_i|,|k_i|≤10^6,~|b_i|≤10^{12}\)
李超线段树，然后不会了
24
标签：10,15,int,2024.9,样例,long,Shintaro,text From： https://www.cnblogs.com/white-ice/p/18415738