当前位置:网站首页>CAIP2021 初赛VP
CAIP2021 初赛VP
2022-07-07 21:50:00 【HeartFireY】
写点小题,放松一下。。。
A.7-1 懂的都懂
暴力打表,然后 O ( 1 ) O(1) O(1)回答询问即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
map<int, bool> mp;
inline void solve(){
int n = 0, k = 0; cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
for(int k = j + 1; k <= n; k++){
for(int l = k + 1; l <= n; l++){
mp[a[i] + a[j] + a[k] + a[l]] = true;
}
}
}
}
for(int i = 1; i <= k; i++){
int m; cin >> m;
bool flag = true;
for(int i = 1; i <= m; i++){
int x; cin >> x;
if(!mp.count(x * 4)) flag = false;
}
if(flag) cout << "Yes\n";
else cout << "No\n";
}
}
signed main(){
solve();
return 0;
}
B.7-2 芬兰木棋
分象限和坐标轴按斜率排序,然后每个区域按顺序进行遍历,动态改变方向统计即可。
最大分数一定是所有木棋之和。可以assert检验答案对不对。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, JD = 1e-5;
struct node{
int x, y, p;
double dis, k;
const bool operator< (const node & x) const {
return k < x.k || fabs(k - x.k) <= JD && dis < x.dis; }
}a[9][N];
int num[9] = {
0};
inline void solve(){
int n = 0; cin >> n;
//int sum = 0;
for(int i = 1; i <= n; i++){
int x, y, p; cin >> x >> y >> p; //sum += p;
double dis = pow((double)(x * x + y * y), 0.5);
double k = 1.0 * y / (1.0 * x);
if(x > 0 && y > 0) a[1][++num[1]] = {
x, y, p, dis, k};
if(x < 0 && y > 0) a[2][++num[2]] = {
x, y, p, dis, k};
if(x < 0 && y < 0) a[3][++num[3]] = {
x, y, p, dis, k};
if(x > 0 && y < 0) a[4][++num[4]] = {
x, y, p, dis, k};
if(x > 0 && y == 0) a[5][++num[5]] = {
x, y, p, dis, 0};
if(x < 0 && y == 0) a[6][++num[6]] = {
x, y, p, dis, 0};
if(x == 0 && y > 0) a[7][++num[7]] = {
x, y, p, dis, 0};
if(x == 0 && y < 0) a[8][++num[8]] = {
x, y, p, dis, 0};
}
for(int i = 1; i <= 8; i++) sort(a[i] + 1, a[i] + 1 + num[i]);
int cnt = 0, ans = 0, ansop = 0;
for(int x = 1; x <= 8; x++){
for(int i = 1; i <= num[x]; i++){
if(fabs(a[x][i].k - a[x][i - 1].k) <= JD){
if(a[x][i].p == 1) cnt++;
else{
if(cnt) ansop++, ans += cnt, cnt = 0;
ansop++, ans += a[x][i].p;
}
}
else{
if(cnt) ansop++, ans += cnt, cnt = 0;
if(a[x][i].p == 1) cnt++;
else ansop++, ans += a[x][i].p;
}
}
if(cnt) ansop++, ans += cnt, cnt = 0;
}
//assert(sum == ans);
cout << ans << ' ' << ansop << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
solve();
return 0;
}
C.7-3 打怪升级
先跑Floyd再跑Dijkstra,代码没存…
属于是什么算法都能杂一起了。。。
D.7-4 疫情防控
典中典之并查集维护倒序加点
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
vector<int> g[N];
struct unionfind{
int par[N];
unionfind(int n) {
for(int i = 1; i <= n; i++) par[i] = i; }
int find(int u){
return (u == par[u] ? u : par[u] = find(par[u])); }
void merge(int u, int v){
int fau = find(u), fav = find(v);
if(fau != fav) par[fav] = u;
}
};
bitset<N> vis;
using pii = pair<int, int>;
struct query{
int c, q;
vector<pii> qu;
}a[N];
int ans[N];
inline void solve(){
int n, m, d; cin >> n >> m >> d;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vis.reset();
for(int i = 1; i <= d; i++){
int c, q; cin >> c >> q;
vis[c] = true;
a[i] = {
c, q};
for(int j = 1; j <= q; j++){
int u, v; cin >> u >> v;
a[i].qu.emplace_back(pii{
u, v});
}
}
unionfind uf(n);
for(int i = 1; i <= n; i++){
if(!vis[i]){
for(auto v : g[i])
if(!vis[v]) uf.merge(i, v);
}
}
for(int i = d; i >= 1; i--){
int cnt = 0;
for(auto q : a[i].qu){
if(uf.find(q.first) != uf.find(q.second)) cnt++;
}
int u = a[i].c;
vis[u] = false;
for(auto v : g[u]){
if(!vis[v]) uf.merge(u, v);
}
ans[i] = cnt;
}
for(int i = 1; i <= d; i++) cout << ans[i] << endl;
}
signed main(){
solve();
return 0;
}
边栏推荐
- 解决:信息中插入avi格式的视频时,提示“unsupported video format”
- Introduction to redis and jedis and redis things
- Line test - graphic reasoning - 1 - Chinese character class
- 网络安全-beef
- V20变频器手自动切换(就地远程切换)的具体方法示例
- Bit operation
- [untitled] reprint melting ice - track icedid server with a few simple steps
- Why does the market need low code?
- Oracle-数据库的备份与恢复
- iNFTnews | NFT技术的广泛应用及其存在的问题
猜你喜欢
Wechat forum exchange applet system graduation design completion (1) development outline
安踏DTC | 安踏转型,构建不只有FILA的增长飞轮
Inftnews | web5 vs Web3: the future is a process, not a destination
Cases of agile innovation and transformation of consumer goods enterprises
微信论坛交流小程序系统毕业设计毕设(2)小程序功能
Unity3D学习笔记6——GPU实例化(1)
Specific method example of V20 frequency converter manual automatic switching (local remote switching)
Comparison of various development methods of applets - cross end? Low code? Native? Or cloud development?
Wechat forum exchange applet system graduation design (2) applet function
Inftnews | the wide application of NFT technology and its existing problems
随机推荐
Two kinds of curves in embedded audio development
Adrnoid开发系列(二十五):使用AlertDialog创建各种类型的对话框
USB(十四)2022-04-12
Cases of agile innovation and transformation of consumer goods enterprises
Binary tree
UE4_UE5全景相机
每日一题——PAT乙级1002题
Guessing game (read data from file)
ArcGIS: field assignment_ The attribute table field calculator assigns values to fields based on conditions
When copying something from the USB flash disk, an error volume error is reported. Please run CHKDSK
微信论坛交流小程序系统毕业设计毕设(7)中期检查报告
kubernetes的简单化数据存储StorageClass(建立和删除以及初步使用)
Network security - install CentOS
Network security - joint query injection
Brush question 3
网络安全-安装CentOS
定位到最底部[通俗易懂]
Dynamics 365 查找字段过滤
智慧社区和智慧城市之间有什么异同
Digital collections accelerated out of the circle, and marsnft helped diversify the culture and tourism economy!