【算法竞赛学习】csoj：寒假第一场
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
文章目录
前言
由于本人菜鸡所以大多都是使用出题人的代码和思路
如有侵权麻烦联系up删帖本贴仅作为笔记记录
本篇大多是在吹水技术方面可以直接看代码注释思路在水文中直接看代码也是可以看得懂的
新年礼物
题目链接
模拟能过本人是使用结构体构造一个nodenode包含p和w其实不这样做也是一样的只是我这么做可以让自己思路更清晰一些
不过我太久没做算法了脑子转的很慢debug了很久再加上在老家很多自己的事情不能自己做学习效率不高。。。做这个的时候我还在吃饭以至于这场只做了这一题。。。。
直接看代码吧
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);//解除绑定可以使cin,cout与scanf,printf一样快但是如果使用这个的话不能将cin/cout与scanf/printf混用只可用其中一种
int n;
cin >> n;
vector<int> p(n), w(n);//分配大小为n
for (auto &x : p)//赋值给p向量
{
cin >> x;
}
for (auto &x : w)
{
cin >> x;
}
int id = 0, ans = 0;
for (int i = 1; i < n; i++)
{
if (p[i] > p[id])
{
if (w[i] < w[id])
ans++;
id = i;
}
}
cout << ans << endl;
return 0;
}
灯笼展
题目链接
这题我第一反应是用set因为STL的关联容器除无序容器外都会以logn的时间复杂度自动排序因为set和map之中是由平衡二叉树构建的。但在后面debug时发现其实set是不对的应该使用multiset因为元素可能重复本人这个代码可以过题。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,k;
cin>>n;
cin>>k;
multiset<int>a;
for(int i=0;i<k;i++)
{
int c;
cin>>c;
cout<<-1<<endl;
a.insert(c);
}
for(int i=k;i<n;i++)
{
int c;
cin>>c;
auto d=a.begin();
for(int i=1;i<k;i++)
{
++d;
}
if(c>=*d)
{
cout<<*d<<endl;
}
else
{
cout<<-1<<endl;
a.insert(c);
}
}
return 0;
}
当然其实用优先队列更加方便。后面看群里人发出的
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,k;
cin>>n;
cin>>k;
priority_queue<int>a;
for(int i=0;i<k;i++)
{
int c;
cin>>c;
cout<<-1<<endl;
a.push(c);
}
for(int i=k;i<n;i++)
{
int c;
cin>>c;
if(c>=a.top())cout<<a.top()<<endl;
else{
cout<<-1<<endl;
a.pop();
a.push(c);
}
}
return 0;
}
摩天楼
题目链接
这个摩天楼不如叫做搬砖🤷♂️
第一反应也是模拟
但是我是想着用stack模拟每次都复制前一秒的stack
但超时了
因为在复制的时候随着栈越来越多复制的时间会越长但其实除了栈顶元素很多元素都是重复的所以还是采用单向链表比较省时间和空间。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int val;
node *pre;
};
int main()
{
ios::sync_with_stdio(0);
node *root = new (node){-1, 0};//0也可以表示NULL初始化默认一一对应即-1对应val0对应pre
auto cur = root;
int n;
cin >> n;
vector<node *> a(n + 1);//存储node指针采用vector作为链表
for (int i = 1; i <= n; i++)
{
string s;
int x;
cin >> s;
if (s[0] != 'R')
cin >> x;
if (s[0] == 'A')
{
cur = new (node){x, cur};
}
if (s[0] == 'R')
{
if (cur->pre)
cur = cur->pre;
}
if (s[0] == 'L')
{
cur = a[x];
}
a[i] = cur;
cout << cur->val << '\n';
}
return 0;
}
这个也是出题人的代码写的比我自己的好很多所以就贴上来了。
神抽
题目链接
看了样例其实基本都知道怎么做了就是在存储的时候记录不然复杂度可能会高。
最主要的还是在逆元处理方面可以直接套快速幂的模板。
逆元是什么可以参考一下我的另一篇逆元
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 998244353;
ll powmod(ll a, ll b)
{
ll r = 1;
while (b)
{
if (b & 1)
r = r * a % p;
a = a * a % p;
b >>= 1;
}
return r;
}
int main()
{
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<int> cnt(1e6 + 5), f(1e6 + 5);
for (int i = 0; i < n; i++)
{
int k;
cin >> k;
for (int j = 0; j < k; j++)
{
int a;
cin >> a;
cnt[a]++;
f[a] = (f[a] + powmod(k, p - 2) * powmod(n, p - 2) % p) % p;//可以把powmod(k, p - 2) 看作1/k,powmod(n, p - 2) 看作1/n整个就是1/(nk)。f[a]=(f[a]+...这边还要加f[a]是因为每个角色池中都可能含有a这个角色
}
}
ll ans = 0;
for (int i = 1; i <= 1e6; i++)
{
ans = (ans + 1ll * f[i] * cnt[i] % p * powmod(n, p - 2) % p) % p;
}
cout << ans << endl;
return 0;
}
新年大礼
题目链接
这题的话可以通过遍历的方式找一下规律当然了这样是过不了题的。
然后就可以找到规律了所有的编号都是从1开始的所以在管理员之中最大编号的后面的非管理员id=k+管理员的数量那么对于非最大管理员编号也是一样的也就是这个非管理员id=k+这个非管理员之前的管理员数量。
关键在于怎么计算管理员数量。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<ll> a(n);
for (auto &x : a)
cin >> x;
sort(a.begin(), a.end());//记得排序
while (q--)
{
ll k;
cin >> k;
int l = 0, r = n;//意味着[)
while (l < r)//l<r的作用在于后面else的处理
{
int mid = l + r >> 1;//相当于(l+r)/2;
if (k + mid + 1 > a[mid])//mid表示a[mid]之前的管理员数量+1表示包括a[mid]
l = mid + 1;//如果待查询的非管理员id>a[mid]则说明该非管理员id在mid后面所以不用包含a[mid]即l=mid+1而非l=mid
else
r = mid;//若待查询的非管理员id<=a[mid]则r=mid为什么不能是r=mid-1呢是因为while(l<r)并且该二分是[)所以r=mid已经排除了a[mid]了其实id只能<a[mid]因为id=a[mid]时是管理员但我们查询的是非管理员。
}
cout << k + l << '\n';
}
return 0;
}