2022河南萌新联赛第(一)场:河南工业大学
Alice and Bob
Nim游戏的变形,Nim游戏是最后不能操作的失败,但是这个游戏是最后把石子取完的人输
先手必胜的条件为:
①:所有堆的异或和不为0,且存在一堆石子的数量大于1
②:所有堆的异或和为0,且所有堆的数量全为1
此时满足上述一个条件 先手必胜
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
int main()
{
LL n;cin >> n;
bool flag = false;//判断是否全为1
LL res = 0;
for(LL i = 2; i <= n / i; i ++)
{
if(n % i == 0)
{
int cnt = 0;
while(n % i == 0)
{
n /= i;
cnt ++;
}
if(cnt > 1)flag = true;
res ^= cnt;
}
}
if(n > 1) res ^= 1;
if((res && flag) || (!flag && res == 0))cout << "Alice win" << endl;
else cout << "Bob win" << endl;
return 0;
}
打对子
用桶数组来判断即可
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
int ton1[N],ton2[N];
int main()
{
int n;cin >> n;
string s1,s2;
cin >> s1 >> s2;
for(int i = 0; i < s1.size(); i ++)
ton1[s1[i] - 'A'] ++;
for(int i = 0; i < s2.size(); i ++)
ton2[s2[i] - 'A'] ++;
int res1 = 0,res2 = 0;
for(int i = 0; i < 30; i ++)
{
res1 += ton1[i] % 2;
res2 += ton2[i] % 2;
}
if(res1 >= res2)cout << res1 << endl << "NO" << endl;
else cout << res1 << endl << "YES" << endl;
return 0;
}
纪念品领取
关键问题是怎样模拟将某个数往后放这个操作
我们可以用每个数被放的时间作为索引进行排序,这样就能使没有被移动的在前面
被移动的在后面
本题的要点是用每个数被点到的时间来维护顺序
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N = 1e5 + 10;
int a[N];//用来存被放到后面的时间
int main()
{
int n,m;cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int x;cin >> x;
a[x] = i;//更新到最新的值
}
vector<PII>q;
for(int i = 1; i <= n; i ++)
q.push_back({a[i],i});
sort(q.begin(),q.end());
vector<int>res;
for(int i = 0; i < 5; i ++)
res.push_back(q[i].second);
sort(res.begin(),res.end());
for(auto x : res)cout << x << " ";
return 0;
}
聚会
分类讨论:
将所有数从小到大排序
假设前i-1个数已经能拼凑出[1,x]
如果ai > x + 1,那么x+1必不能被凑出
如果ai <= x + 1,那么范围可以扩大为[1,x + ai]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N = 1e5 + 10;
int a[N];//用来存被放到后面的时间
int main()
{
int n;cin >> n;
for(int i = 0; i < n; i ++)cin >> a[i];
sort(a,a + n);
LL ed = 0;
for(int i = 0; i < n; i ++ )
{
if(a[i] > ed + 1)
{
cout << ed + 1 << endl;
return 0;
}
else ed = a[i] + ed;
}
cout << ed + 1 << endl;
return 0;
}
买车
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N = 1e5 + 10;
PII a[N];
//贪心策略:每次选能到达的最远位置
//按照左端点进行排序,然后在优先队列中选则能到达的最远位置
int main()
{
//t存的是他能到达的最远的位置
int n,m,t;cin >> n >> m >> t;
for(int i = 0; i < m; i ++)
{
int x,y;cin >> x >> y;
a[i] = {x,y};
}
sort(a, a + m);
int res = 0;
priority_queue<int>q;//用来维护最远能到达的位置
for(int i = 0; i < m; i ++)
{
if(a[i].first > t)//说明当前情况走不到下一个了,还有一次机会看是否能更新
{
if(!q.empty() && q.top() >= a[i].first)
t = q.top(),res ++;//每次更新距离都是一次换车过程
else //如果无法更新,那么就输出-1
{
cout << -1 << endl;
return 0;
}
}
//里面存的都是合法的最远位置
q.push(a[i].first + a[i].second);
}
if(max(q.top(),t) < n)cout << -1 << endl;
else cout << res << endl;
return 0;
}
热身小游戏
Acwing 3001. 数学计算
在这道题的基础上加了一个懒标记
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N = 1e5 + 10,mod = 1e9 + 7;
struct Edge
{
int l,r;
LL lazy,sum;//维护的是区间乘的数是多少
//懒标记表示将当前区间的sum置成1
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = (LL)tr[u << 1].sum * tr[u << 1 | 1].sum % mod;
}
void pushdown(int u)//父节点更新子节点
{
auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
if(root.lazy)
{
left.lazy = 1,left.sum = 1;
right.lazy = 1,right.sum = 1;
root.lazy = 0;
}
}
void build(int u,int l,int r)
{
tr[u] = {l,r,0,1};
if(l == r)return;
int mid = l + r >> 1;
build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
pushup(u);
}
void modify(int u,int l,int r,int c)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].lazy = 1;
tr[u].sum = c;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)modify(u << 1,l,r,c);
if(r > mid) modify(u << 1 | 1,l,r,c);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum;
else
{
LL res = 1;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)res *= query(u << 1,l,r) % mod;
if(r > mid)res *= query(u << 1 | 1,l,r) % mod;
return res;
}
}
int main()
{
int q;cin >> q;
build(1,1,q);
for(int i = 1; i <= q; i ++)
{
int op;cin >> op;
if(op == 1)
{
int a;cin >> a;
modify(1, i, i, a);
}
else if(op == 2)
{
int l,r;cin >> l >> r;
modify(1,l,r,1);
}
else cout << query(1,1,q) << endl;
}
return 0;
}
巡逻机器人
我们要枚举每个机器人的运动轨迹,可以用两个数组来是他们产生关联
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N = 1e6 + 10,mod = 1e9 + 7;
bool vis[N];
int d[N],p[N];//p用来存每个机器人走到的位置,d用来存每个机器人走的步数
int main()
{
int n,m;cin >> n >> m;
int cnt = 0;//可能有重复结点
for(int i = 1; i <= m; i ++)
{
char op;cin >> p[i] >> op;
if(op == 'L')d[i] = -1;
else d[i] = 1;
if(!vis[p[i]])
vis[p[i]] = true,cnt ++;
}
int res = 0;
while(cnt < n)
{
res ++;
for(int i = 1; i <= m; i ++)
{
p[i] += d[i];
if(p[i] == n + 1)p[i] = 1;
if(p[i] == 0)p[i] = n;
if(!vis[p[i]]) vis[p[i]] = true,cnt ++;
}
}
cout << res << endl;
return 0;
}
糟糕的一天
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N = 1e6 + 10;
int a[N];
int main()
{
int n;cin >> n;
int res = 0;
for(int i = 1; i <= n; i ++)cin >> a[i];
int mx = a[n];
for(int i = n - 1; i ; i --)
{
if(a[i] < mx)res ++;
mx = max(mx, a[i]);
}
cout << res << endl;
return 0;
}
樱果运输
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int>PII;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int f[N][1010];//从前j辆车中选,总价值不超过k的最大载重
int w[N], v[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++)cin >> w[i] >> v[i];
for (int i = 1; i <= n; i ++)//看怎样选车能得到最大载重
for (int j = i; j >= 1; j --)
for (int k = 1000; k >= w[i]; k --) {
//枚举所有的车,得到最大的j辆车,价钱k的最大载重
f[j][k] = max(f[j][k], f[j - 1][k - w[i]] + v[i]);
}
while (m --) {
int x, y;
cin >> x >> y;
int res = -1;
for (int i = 1; i <= n; i ++)
if (f[i][x] >= y) {
res = i;
break;
}
cout << res << endl;
}
return 0;
}