2019icpc西安邀请赛
来源:https://www.jisuanke.com/contest/2625?view=challenges
更新中
A.Tasks
直接贪心
代码:听说当时很多队伍提前拆题甚至上机了,所以很多0min
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 1e6+;
const int maxm = 6e6+;
//const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MAXN = maxn;
const int MAXM = maxm;
const db pi = acos(-1.0); int n, t;
int a[maxn];
int main() {
scanf("%d %d" ,&n ,&t);
for(int i = ; i < n; i++){
scanf("%d", &a[i]);
}
sort(a,a+n);
int tmp = ;
int ans = ;
for(int i = ; i < n; i++){
if(tmp+a[i]<=t){
tmp+=a[i];ans++;
} }printf("%d", ans);
return ;
}
C.Angel's Journey
题意:给定一个圆的圆心(rx, ry),半径r,A的坐标(rx, ry-r),B的坐标(x, y),y>ry,只能走圆上以及圆外y>ry的地方,求A到B的最短路
思路:当x<rx-r或x>rx+r的时候直接从半圆的地方走直线,否则在圆弧上走到切点然后走直线
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 1e6+;
const int maxm = 6e6+;
//const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MAXN = maxn;
const int MAXM = maxm;
const db pi = acos(-1.0); int n, t;
int a[maxn];
int main() {
double rx,ry,r,x,y;
int t;
scanf("%d" ,&t);
while(t--){
scanf("%lf %lf %lf %lf %lf", &rx,&ry,&r,&x,&y); double ob = sqrt((x-rx)*(x-rx)+(y-ry)*(y-ry));
double ans = sqrt(ob*ob-r*r)+r*(pi/2.0+asin((y-ry)/ob)-acos(r/ob));
if(x<rx-r||x>rx+r){
if(x<rx-r)rx-=r;
if(x>rx+r)rx+=r;
ans=pi/+sqrt((x-rx)*(x-rx)+(y-ry)*(y-ry));
}
printf("%.4lf\n",ans);
}
return ;
}
D.Miku and Generals
题意:n个数,还有m对矛盾的数,n,m<=200,a[i]<=5e4&&(a[i]%100==0),矛盾的不能放在一堆,让你分配这两堆数(都要用完),使得两堆数的和之差最小,输出那个最大的数
思路:将矛盾的值连无向边,因为答案是保证存在的,所以对每一个连通块只有两种选法,通过dfs染色把它们提出来,就是一个背包了,由于a[i]%100==0,所以先除了最后再补俩零也不影响
代码:我tm最后才发现那个a[i]能整除100。。复杂度downdown
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 1e7+;
const int maxm = 6e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int n, m;
vector<int>v[maxn/];
int vis[maxn/];
int a[maxn/];
int f[maxn]; void dfs(int x, int fa, int faa, int co){
if(vis[x]!=-)return;
if(co){
if(x!=fa){a[fa]+=a[x];a[x]=-;}
vis[x]=fa;
}
else{
if(x!=faa){a[faa]+=a[x];a[x]=-;}
vis[x]=faa;
}
int t;
if(x==fa&&v[x].size()>)t = v[x][];
else t=faa;
for(int i = ; i < (int)v[x].size(); i++){
int y = v[x][i];
if(vis[y]==-){
dfs(y,fa,t,co^);
} }
}
bool cmp(int a,int b){return a>b;}
int main() {
int t;
scanf("%d" ,&t);
int ncase = ;
while(t--){
scanf("%d %d" ,&n, &m);
//mem(f,0);
ncase++;
int sum = ;
for(int i = ; i <= n; i++){
v[i].clear();
vis[i]=-;
scanf("%d", &a[i]);a[i]/=;sum+=a[i];
}
for(int i = ; i <= m; i++){
int x,y;
scanf("%d %d" ,&x, &y);
v[x].pb(y);
v[y].pb(x);
}
for(int i = ; i <= n; i++){
if(vis[i]==-){
dfs(i,i,,);
}
}
sort(a+,a++n,cmp);
int ans=;
f[]=ncase;
for(int i = ; i <= n; i++){
if(a[i]==-)break;
for(int j = sum; j >= ; j--){
if(j-a[i]>=&&f[j-a[i]]==ncase){
//printf(" %d \n",j);
f[j]=ncase;
if(j<=sum/)ans=max(ans,j);
}
}
}
printf("%d00\n",sum-ans);
} return ;
}
J.And And And
题意:一棵有边权的树,对每一对(u,v),如果u到v路径上边权异或和为0,则它对答案的贡献为包含这条路径的树上路径数量,求总答案
思路:以1为根,预处理出各个子树的size,对每一对满足条件的(u,v),因为树上的路径是唯一的,它的贡献应该是u除这条路径外能走的点数*v除这条路径外能走的点数,当u和v在不同链上的时候,答案就是size[u]*size[v];若u和v在同一条链上,其中一个点(例如v)如果是深度较大的点,那么后者就是size[v],前者可以动态统计。
于是可以直接dfs,因为dfs的时候走下来就是一条链,回溯之后就是另一条链,所以在处理同一条链的时候我们可以统计当前点为u时的贡献即可。不同链的时候,我们让它dfs到底,当当前点处理完之后,说明这条链搞完了,就可以一条链一条链更新了,这个看代码好像比较好理解。。。
对了,u到v路径异或和为0可以转化为到根的异或和相等。
代码:long long很烦,而且深搜好像并不需要记录fa。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<unordered_map> #define fst first
#define sc second
#define pb push_back
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 1e5+;
const int maxm = 6e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int n;
vector<pair<int,ll> >v[maxn];
int sz[maxn];
void dfsInit(int x, int fa){
sz[x]++;
for(int i = ; i < (int)v[x].size(); i++){
int y = v[x][i].fst;
if(y!=fa){
dfsInit(y,x);
sz[x]+=sz[y];
}
}
}
ll ans;
unordered_map<ll,int> num;// the value of gongxian in sta == i
ll tmp;
void dfs1(int x, int fa, ll sum){//the same line
ans += 1ll*num[sum]*sz[x];
ans%=mod;
for(int i = ; i < (int)v[x].size(); i++){
int y = v[x][i].fst;
ll w = v[x][i].sc;
if(y!=fa){
tmp=(tmp+sz[x]-sz[y]+mod)%mod;
num[sum]=(num[sum]+tmp)%mod;
dfs1(y,x,sum^w);
num[sum]=(num[sum]-tmp+mod)%mod;
tmp=(tmp-(sz[x]-sz[y])+mod)%mod;
}
}
}
void dfs2(int x, int fa, ll sum){
ans += 1ll*num[sum]*sz[x];
ans%=mod;
for(int i = ; i < (int)v[x].size(); i++){
int y = v[x][i].fst;
ll w = v[x][i].sc;
if(y==fa)continue;
dfs2(y,x,sum^w);
}
num[sum]+=sz[x];
num[sum]%=mod;
}
int main() {
tmp=ans=;
scanf("%d" ,&n);
for(ll i = ; i <= n; i++){
int x;
ll w;
scanf("%d %lld", &x, &w);
v[x].pb(mp(i,w));
v[i].pb(mp(x,w));
}
dfsInit(,);
dfs1(,,);
num.clear();
dfs2(,,);
printf("%lld",ans);
return ;
}
L.Swap
题意:一个排列可以交换前n/2与后n/2,或前n^1个数奇数位置和偶数位置交换,问通过这两个操作最多产生多少个不同的排列
思路:打表发现从第五项开始是2n, n, 12, 4的规律。或者直接交上打表的模拟,由于只有两条链,而且只有一组数据,也能过
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 1e6+;
const int maxm = 6e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int n;
int a[maxn],b[maxn];
int ans;
void gao1(int a[]){
int l = ;
int r = n/+;
if(n&)r++;
for(int i = ; i <= n/; i++){
swap(a[l+i-],a[r+i-]);
}
return;
}
void gao2(int a[]){
for(int i = ; i+ <= n; i+=){
//printf(" %d %d %d\n",i,a[i],a[i+1]);
swap(a[i],a[i+]);
}
return;
} int sv(int n){
::n=n;
ans=;
int sta=;
for(int i = ; i <= n; i++)a[i]=b[i]=i;
/*if(n==1)return 1;
if(n==2)return 2;
if(n==3)return 6;*/
gao1(a);gao2(b);
//for(int i = 1; i <= n; i++)printf("%d ",a[i]);printf("\n");
//for(int i = 1; i <= n; i++)printf("%d ",b[i]);printf("\n");
while(){
//for(int i = 1; i <= n; i++)printf("%d ",a[i]);printf("\n");
//for(int i = 1; i <= n; i++)printf("%d ",b[i]);printf("\n");
int ys = ;
sta^=;
for(int i = ; i <= n; i++){
if(a[i]!=b[i])ys=;
}
if(!ys){
ans++;break;
}
else{
ans+=;
if(sta) {gao1(a);gao2(b);}
else {gao1(b);gao2(a);}
}
}
return ans;
}
int main() {
//scanf("%d" ,&n);
//sv(3);
for(int i = ; i <= ; i++){
printf("%d %d\n",i,sv(i));
}
scanf("%d", &n);
//for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
printf("%d",sv(n));
return ;
}
M.Travel
题意:一个有边权的无向图,刚开始无边可走,每次操作可以增加e条边,增加d点能量,每次操作花费c,问从1走到n最少花费多少,只有这条边加了并且能量不小于边权才能走
思路:我第n次sb。。很明显的二分,而我妄图一次dijk搞完,就把自己搞完了。
很显然操作次数具有单调性,并且因为保证联通,所以答案一定存在。
代码:因为改了很多次,所以很丑
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 1e6+;
const int maxm = 6e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int vis[maxn];
struct node{
int id,w;
node(int a, int b){id=a;w=b;}
bool operator < (const node & a) const{
return w>a.w;
}
};
vector<node>v[maxn];
int n,m;
int c, d, e;
bool ck(int k){
//printf(" %d\n",k);
for(int i = ; i <= n; i++)vis[i]=;
queue<PI>q;
q.push(make_pair(,));
while(!q.empty()){
PI top = q.front();q.pop();
int x = top.fst;
int d = top.sc;
//printf("%d %d ----%d\n",x,d);
if(x==n){
if(d<=1ll*e*k)return true;
else return false;
}
if(vis[x])continue;
vis[x]=;
for(int i = ; i < (int)v[x].size(); i++){
node y = v[x][i];
//printf(" %d %d\n",y.id,y.w);
if(!vis[y.id]&&1ll*y.w<=1ll*(::d)*k)q.push(make_pair(y.id,d+));
}
}
return false;
}
int main() { scanf("%d %d", &n, &m);
scanf("%d %d %d" ,&c, &d, &e);
for(int i = ; i <= m; i++){
int x,y,w;
scanf("%d %d %d" ,&x, &y, &w);
v[x].pb(node(y,w));
v[y].pb(node(x,w));
}
int l, r;
l = ; r = 1e5+;
int ans = -;
while(l<=r){
int mid = (l+r)>>;
if(ck(mid)){
ans = mid;
r=mid-;
}
else l= mid+;
}
printf("%lld",1ll*c*ans);
return ;
}
/*
3 3
1 99 1
1 2 100
1 3 100
2 3 2
*/
最新文章
- 循序渐进Python3(十)-- 0 -- RabbitMQ
- Devexpress VCL Build v2014 vol 15.2.3 发布
- 操作ACCESS数据库注意事项
- NEST.net Client For Elasticsearch简单应用
- How to tune SharePoint 2010 Server for better performance?
- vue学习之vuex
- Spring Boot 集成Swagger
- Session &;cookie introduction,usage
- shell编程基础(二): shell脚本语法之分支语句和循环语句
- 在windows上搭建SSH服务踩过的坑
- first time to use github
- DB2 create tablespace
- python 遍历list并删除部分元素
- DedeCMS后台500错误一种原因是不支持PHP5.3、5.4及以上版本
- 如何将img垂直居中?
- 【C】——setvbuf(scanf内存溢出问题)
- linux下设置软件使用socks5代理
- 如何合理的规划jvm性能调优
- Java多线程编程实战指南(核心篇)读书笔记(三)
- ascII、iso、utf-8、Unicode的区别