当前位置:网站首页>Caip2021 preliminary VP
Caip2021 preliminary VP
2022-07-07 23:21:00 【HeartFireY】
Write some questions , Take it easy ...
A.7-1 Know everything.
Watch violence , then O ( 1 ) O(1) O(1) Just answer the question .
#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 Finnish wood chess
Quadrants and coordinate axes are sorted by slope , Then each region is traversed in order , Dynamically change the direction statistics .
The maximum score must be the sum of all wooden chess . Sure assert Check the answer .
#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 Have to upgrade
Run first Floyd Run again Dijkstra, Code not saved …
Any algorithm can be mixed ...
D.7-4 Epidemic prevention and control
Add points in reverse order for the maintenance of the joint search set of codes in codes
#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;
}
边栏推荐
- Cloud native is devouring everything. How should developers deal with it?
- Install a new version of idea. Double click it to open it
- What are the similarities and differences between smart communities and smart cities
- Talk about the design and implementation logic of payment process
- 统计电影票房排名前10的电影并存入还有一个文件
- Kubernetes' simplified data storage storageclass (creation, deletion and initial use)
- 网络安全-对操作系统进行信息查询
- 云原生数据仓库AnalyticDB MySQL版用户手册
- USB (十七)2022-04-15
- leetcode-520. Detect capital letters -js
猜你喜欢
ROS2专题(03):ROS1和ROS2的区别【02】
LDO voltage stabilizing chip - internal block diagram and selection parameters
In the field of software engineering, we have been doing scientific research for ten years!
海内外技术人们“看”音视频技术的未来
LeeCode -- 6. Z 字形变换
Inftnews | web5 vs Web3: the future is a process, not a destination
JMeter interface automated test read case, execute and write back result
PMP项目管理考试过关口诀-1
成年人只有一份主业是要付出代价的,被人事劝退后,我哭了一整晚
【微服务|SCG】gateway整合sentinel
随机推荐
微信论坛交流小程序系统毕业设计毕设(1)开发概要
Unity3D学习笔记4——创建Mesh高级接口
Clean C disk
Vulnerability recurrence ----- 49. Apache airflow authentication bypass (cve-2020-17526)
Wechat forum exchange applet system graduation design completion (4) opening report
Talk about the design and implementation logic of payment process
How to generate unique file names
turbo intruder常用脚本
[microservices SCG] gateway integration Sentinel
微信论坛交流小程序系统毕业设计毕设(5)任务书
Network security -beef
网络安全-安装CentOS
GEE(四):计算两个变量(影像)之间的相关性并绘制散点图
网格(Grid)
Bit operation
When copying something from the USB flash disk, an error volume error is reported. Please run CHKDSK
UE4_UE5全景相机
Cloud native data warehouse analyticdb MySQL user manual
Grid
USB(十六)2022-04-28