Helvetic Coding Contest 2019 online mirror (teams allowed, unrated)

2023-08-10 04:57:46

http://codeforces.com/contest/1184

A1

找一对整数,使x^x+2xy+x+1=r

变换成一个分式，保证整除

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 300050;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
ll r;
int main(){r=read();for(ll i = 1;i <= 1000000;i++){if(i*i>r)break;ll t = r-i*i-i-1;if(t<=0)continue;if(t%(i+i)==0){cout<" "<i);return 0;}}cout<<"NO";return 0;
}
View Code

A2

给定一个二进制串，对于整数k来说，若存在另一个二进制串x，时x与x右移k位异或的结果等于这个二进制串，k就是合法的，求合法的k的数量。

先考虑x，第一个位确定了，后面1+k,1+2k...的位也确定了，最后会回到第一位，这时需要与之前假定的第一位一致。于是这就形成了一个循环。循环长度为lcm(k,n)/k=n/gcd(k,n)。

对k，按gcd(k,n)，进行归纳求解，将所有k映射到gcd(k,n)，然后求出gcd(k,n)的答案，只需要遍历所有循环的位置，再查看是否合法。

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 200050;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int n;
int a[maxn];
char s[maxn];
bool vis[maxn];
bool can[maxn];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);
}
int main(){n=read();scanf("%s",s+1);fo(i,1,n){a[i] = s[i] - '0';}int ans = 0,tot = 0;fo(i,1,n){int g = gcd(i,n);if(vis[g]){ans += can[g];}else{vis[g]=true;bool ok=false;fo(j,1,g){ok=true;tot=0;for(int k = j;k <= n;k += g){tot += a[k];}if(tot%2){ok=false;break;}}if(ok) can[g]=true;ans += can[g];}}cout<<ans;return 0;
}
View Code

B1

舰队攻打敌军，只能攻打防御力不大于它攻击力的，敌军掉落的金币不等，问每个船能打多少钱

排序即可

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 200050;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int s,b;
struct dat{int pos;int val;friend bool operator < (dat a,dat b){return a.val < b.val;}
}shp[maxn],ene[maxn];
ll gold[maxn];
int main(){s=read();b=read();fo(i,1,s){shp[i].pos=i;shp[i].val=read();}fo(i,1,b){ene[i].val=read();ene[i].pos=read();}sort(shp+1,shp+1+s);sort(ene+1,ene+1+b);int pos=0;ll ans = 0;fo(i,1,s){while(pos1].val<=shp[i].val){pos++;ans += ene[pos].pos;}gold[shp[i].pos]=ans;}fo(i,1,s){printf("%I64d ",gold[i]);}return 0;
}
View Code

B2

敌军在一个图上攻打舰队，每个敌军只能打防御力不大于他的船，并且两者距离不大于他的燃油量。每个敌军负责打一个人，掠夺k金币。

我军可以花h金币建造假船，一定会被一个敌军攻击，且不损失金币。求损失最少的策略。

因为金币数量是固定的，容易证明要么全用假船吸引，要么一个假船都不放。

先跑多源最短路，然后匹配即可。

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 200050;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int n,m;
int dis[105][105];
int s,b;
ll kk,hh;
struct ship{int x;ll f;ll a;
}ships[1050];
struct ene{int x;ll d;
}enes[1050];
int uN,vN;
int g[1050][1050];
int linker[1050];
int used[1050];
bool dfs(int u){for(int v = 0;v < vN;v++){if(g[u][v] && !used[v]){used[v] = true;if(linker[v]==-1||dfs(linker[v])){linker[v]=u;return true;}}}return false;
}
int hungary(){int res = 0;memset(linker,-1, sizeof(linker));for(int u = 0;u < uN;u++){memset(used,false, sizeof(used));if(dfs(u))res++;}return res;
}
int main(){n=read();m=read();int u,v;fo(i,1,n){fo(j,1,n){dis[i][j]=1e7;}dis[i][i]=0;}fo(i,1,m){u=read();v=read();dis[u][v] = 1;}fo(k,1,n){fo(i,1,n){fo(j,1,n){if(k==i||k==j||i==j)continue;dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}}}s=read();b=read();kk=read();hh=read();fo(i,1,s){ships[i].x=read();ships[i].a=read();ships[i].f=read();}fo(i,1,b){enes[i].x=read();enes[i].d=read();}uN=s;vN=b;fo(i,1,s){fo(j,1,b){if(ships[i].a >= enes[j].d && dis[ships[i].x][ships[j].x] <= ships[i].f) g[i-1][j-1]=1;}}ll ans = min((ll)s*hh,kk*hungary());cout<<ans;return 0;
}
View Code

C1

给若干个在长方形边上的点和一个不在边上的点，找出那个长方形

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 55;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int n;
int x[maxn],y[maxn];
bool check(int x1,int x2,int y1,int y2){int cnt = 0,t=0;bool debug=false;if(x1==19&&x2==45&&y1==1&&y2==27)debug=true;fo(i,1,n){if(x[i]x2||y[i]y2){cnt++;t=i;}else if(x[i]!=x1&&x[i]!=x2&&y[i]!=y1&&y[i]!=y2){cnt++;t=i;}if(cnt>1)return false;}if(cnt == 0) return false;cout<" "<<y[t];return true;
}
int main(){n=read();n = n*4+1;fo(i,1,n){x[i]=read();y[i]=read();}fo(i,0,50){fo(j,i,50){fo(k,0,50){fo(l,k,50){if(check(i,j,k,l)) return 0;}}}}return 0;
}
View Code

D1

一个长度n的线段和一个特殊点，每次插入或者切掉头或尾一段，每次询问特殊点的位置。

维护即可。

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 305;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int n,k,m,t;
int main(){n=read();k=read();m=read();t=read();int opt,v;fo(i,1,t){opt=read();v=read();if(opt==1){n++;if(v<=k)k++;}else{if(k > v){n-=v;k-=v;}else{n=v;}}cout<" "<endl;}return 0;
}
View Code

E1

给一个图，求出最小生成树，问如果第一条边可能在最小生成树里，其边权最多是多大

看看什么时候这条边对应的两个点处于同一个集合中。

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 100050;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int n,m;
int f[maxn];
int findf(int x){return f[x]==x?x:f[x]=findf(f[x]);
}
struct edge{int u;int v;ll w;friend bool operator < (edge a,edge b){return a.w < b.w;}
}e[maxn*10];
int main(){n=read();m=read();fo(i,1,m){e[i].u=read();e[i].v=read();e[i].w=read();}fo(i,1,n){f[i]=i;}int aa = e[1].u,bb=e[1].v;sort(e+1,e+1+m);fo(i,1,m){int u=e[i].u;int v=e[i].v;int fu=findf(u),fv=findf(v);if(fu==fv) continue;if(e[i].u==aa&&e[i].v==bb)continue;f[fu]=fv;if(findf(aa)==findf(bb)){cout<<e[i].w;return 0;}}cout<<1000000000;return 0;
}
View Code

E2

与上一个问题类似，但是这次要求除了最小生成树的边之外所有边的答案

先求最小生成树，两个点之间加一条边，则形成一个环，由这条边和两者的树上最短路径的边组成，用lca求最短路径上的边的最大边权即可。

#include
#include
#include<string>
#include
#include
#include
#include
#include
#include 
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
using namespace std;
const int maxn = 100050;
const ll mod = 1e9+7;
inline ll read(){ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
int n,m;
int f[maxn];
int findf(int x){return f[x]==x?x:f[x]=findf(f[x]);
}
struct edge{int u;int v;ll w;int id;friend bool operator < (edge a,edge b){return a.w < b.w;}
}e[maxn*10];
bool chs[maxn*10];
bool cmp(edge a,edge b){return a.id < b.id;
}
int dep[maxn];
int fa[maxn][25];
ll fw[maxn][25];
struct te{int v;ll w;
}now,nxt;
vector g[maxn];
void dfs(int x,int p){int k = 0;   while(fa[x][k]&&fa[fa[x][k]][k]){fa[x][k+1] = fa[fa[x][k]][k];fw[x][k+1] = max(fw[x][k],fw[fa[x][k]][k]);k++;}int sz = g[x].size();int v=0;fo(i,0,sz-1){v=g[x][i].v;if(v==p)continue;fa[v][0] = x;fw[v][0] = g[x][i].w;dep[v] = dep[x] + 1;dfs(v,x);}
}
ll getans(int u,int v){if(dep[u]<dep[v]) swap(u,v);ll mx = 0;int k = 0,dif=dep[u]-dep[v];int ru=u,rv=v;while(dif){if(dif&1){mx = max(fw[u][k],mx);u = fa[u][k];}dif >>= 1;k++;}if(u==v)return mx;k = 0;while(k >= 0){if(fa[u][k] != fa[v][k]){mx = max(mx,fw[u][k]);mx = max(mx,fw[v][k]);u = fa[u][k];v = fa[v][k];k++;}else{k--;}}mx = max(mx,fw[u][0]);mx = max(mx,fw[v][0]);return mx;
}
int main(){n=read();m=read();fo(i,1,m){e[i].u=read();e[i].v=read();e[i].w=read();e[i].id=i;}fo(i,1,n){f[i]=i;}sort(e+1,e+1+m);fo(i,1,m){int u=e[i].u;int v=e[i].v;int fu=findf(u),fv=findf(v);if(fu==fv) continue;f[fu]=fv;chs[e[i].id]=true;now.w=e[i].w;now.v=v;g[u].push_back(now);now.v=u;g[v].push_back(now);}dfs(1,0);sort(e+1,e+1+m,cmp);fo(i,1,m){if(chs[i])continue;printf("%I64d\n",getans(e[i].u,e[i].v));}return 0;
}
View Code

 

转载于:https://www.cnblogs.com/hyfer/p/11165349.html


本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

相关文章

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统 微软输入法 于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销 是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题 跑道 汽车 绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

立即
投稿

微信公众账号

微信扫一扫加关注

 返回
顶部