赣州网站建设价格,东营建设信息网最新招聘,东莞专业网站设计建站公司,网站是用什么做的吗前言
比较水的一场比赛 E题几乎是一本通原题而我还是不会做qwq
A - Sagheer and Crossroads 有一个十字路口#xff0c;给出四个路口的车是否可以左转/右转/直行#xff0c;并且给出每个路口的行人是否可以通过#xff0c;求是否出现车和人冲突的情况 阅读理解题#xff…前言
比较水的一场比赛 E题几乎是一本通原题而我还是不会做qwq
A - Sagheer and Crossroads 有一个十字路口给出四个路口的车是否可以左转/右转/直行并且给出每个路口的行人是否可以通过求是否出现车和人冲突的情况 阅读理解题其实只是我英语太差了读懂题意直接模拟即可
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N5e5100;
const int mod1e97;
const double eps1e-9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;int a[5][5],d[4]{0,3,2,1};
bool vis[5];
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endiffor(int i1;i4;i){for(int j1;j4;j) a[i][j]read();}for(int i1;i4;i){for(int j1;j3;j){if(a[i][j]){//printf(i%d j%d to%d\n,i,j,(id[j]-1)%41);vis[(id[j]-1)%41]1,vis[i]1;}}}for(int i1;i4;i){if(vis[i]a[i][4]){printf(YES);return 0;}}printf(NO\n);return 0;
}
B - Sagheer, the Hausmeister 给出一个n层的房屋每层有m个房间最左边和最右边有两个楼梯 有一些房间的灯是开着的求一条从第一层左楼梯开始的最短的不下楼的路径关掉所有的灯 n≤15,m≤100n \leq 15,m \leq 100n≤15,m≤100 dp入门水题设计 dpi,0/1dp_{i,0/1}dpi,0/1 表示从在第 i 层的左/右楼梯本层的灯还没有关的最短路径枚举关灯方式进行转移即可 时间复杂度 O(n×m)O(n \times m)O(n×m)瓶颈竟然在于输入 但是这题还WA了两次…有一些特殊情况需要特判
如果当前楼的上面一盏灯都没有就不必继续上楼了存在整栋楼没有灯的情况
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N5e5100;
const int mod1e97;
const double eps1e-9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;
int dp[18][2];
int l[18],r[18];
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifint top(0);nread();mread()2;for(int in;i1;i--){for(int j1;jm;j){int x(0);scanf(%1d,x);if(x){if(!top) topi;if(!l[i]) l[i]j;r[i]j;}}}memset(dp,0x3f,sizeof(dp));dp[1][0]0;ntop;if(!top){printf(0);return 0;}for(int i1;in;i){if(!l[i]){dp[i1][0]dp[i][0]1;dp[i1][1]dp[i][1]1;}else{dp[i1][0]min(dp[i][0]2*(r[i]-1)1,dp[i][1]m);dp[i1][1]min(dp[i][1]2*(m-l[i])1,dp[i][0]m);//printf(i%d dp0%d dp1%d\n,i1,dp[i1][0],dp[i1][1]);}}int ansmin(dp[n][0]r[n]-1,dp[n][1]m-l[n]);printf(%d\n,ans);return 0;
}
C - Sagheer and Nubian Market 给出 nnn 个元素的基本价格 aia_iai 如果你选择了k个元素 ax1,ax2,...,axka_{x_1},a_{x_2},...,a_{x_k}ax1,ax2,...,axk那么每个元素的真实价格就是 axik∗xia_{x_i}k*x_iaxik∗xi换句话说就是加上总数量乘下角标 现在有 sss 元钱求最多能买到几个元素 二分答案二分后每个元素的真实价格就确定了sort后取前 kkk 个看有没有超过 sss 即可
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
const int mod1e97;
const double eps1e-9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,s;
ll a[N],b[N];
ll calc(int k){for(int i1;in;i) b[i]a[i]1ll*i*k;sort(b1,b1n);ll res(0);for(int i1;ik;i) resb[i];return res;
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();sread();for(int i1;in;i) a[i]read();int st0,edn;while(sted){int mid(sted1)1;if(calc(mid)s) stmid;else edmid-1;}printf(%d %lld\n,st,calc(st));return 0;
}
D - Sagheer and Kindergarten
如果想自己做一下这道题建议直接去原题面 有 nnn 个孩子和 mmm 个玩具孩子会提出一共k个对玩具的要求满足如下性质 如果一个孩子要求的玩具是闲置的也就是不在任何一个孩子手中,他就会得到那个玩具否则他就会一直等待每个孩子可能会要求得到若干个玩具只有当其得到 所有玩具 时才会满意并在玩一会玩具后返还所有的玩具而在此之前会一直霸占着所有已有的玩具如果变得空闲的玩具被两个孩子要求会优先满足靠前的要求如果一个孩子的某个要求没有被满足他就不会再要求别的玩具如果一个孩子发现自己永远也得不到满足就会开始哭保证在当前的k个要求中没有孩子在哭 有q个独立的询问每次增加一条要求不一定满足第4条和第6条求有多少个孩子在哭 真正的阅读理解题上面这一大陀已经是我部分精简抽象后的结果难点似乎就在于转化题意后面就比较显然了
可以把对玩具的要求转化为孩子之间的依赖关系 具体的如果x要求玩具w上一个要求玩具w的人是y就连一条有向边 y−xy-xy−x表示只有y满足之后x才能满足 一个孩子哭泣当且仅当他在某个环中 由于性质4和性质6连成的图一定是一个森林 每次判断给出的新的依赖关系是否是返祖边如果是这条链就会形成一个环否则必然不会成环 判断返祖不必lca可以直接用dfs序判定子树的方法单次询问 O(1)O(1)O(1)
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
const int mod1e97;
const double eps1e-9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,k,q;
int bel[N];
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}int du[N];
int siz[N],pos[N],tim,dep[N];
void dfs(int x,int f){pos[x]tim;dep[x]dep[f]1;siz[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;dfs(to,x);siz[x]siz[to];}return;
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread();kread();qread();for(int i1;ik;i){int xread(),yread();if(bel[y]) addline(bel[y],x),du[x];bel[y]x; }for(int i1;in;i){if(!du[i]) dfs(i,0);}for(int i1;iq;i){int xread(),yread();int obel[y];if(pos[x]pos[o]pos[o]pos[x]siz[x]-1) printf(%d\n,siz[x]);else printf(0\n);}return 0;
}
E - Sagheer and Apple Tree 给定一个树第i个节点上有aia_iai个苹果 两人轮流行动每次可以选择一个有苹果的节点进行下列行为之一 如果是叶子节点就吃掉节点上的一些苹果如果不是叶子就把节点上的一些苹果移到他的一个儿子上 保证从根到所有叶子的距离的奇偶性相同 现在后手方可以交换任意两个节点(u,v)(u,v)(u,v)上的苹果数求能使双方最优情况下后手获胜的无序点对(u,v)(u,v)(u,v)的数量 ybt有一道情景几乎一模一样的题 然而还是并不会 qwq 感觉这个题的题解讲的更加透彻 把叶子和到叶子距离为偶数的点染成黑色距离为偶数的点染成白色 那么每次操作其实就是使黑色节点的某一堆的石子增加或减少 那么和nim游戏的唯一区别就是这里还可以增加石子 但是其实并不影响因为必败方尝试增加石子后必胜方都可以把增加的石子减少回去 所以后手胜的充要条件和nim一样就是黑点权值异或和为0 然后合法点对就可以分类讨论一下然后开个map随便做了
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
const int mod1e97;
const double eps1e-9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}int num[2];
int a[N],op[N],s;
mapint,intmp;
void dfs(int x){if(fi[x]-1){op[x]1;return;}for(int ifi[x];~i;ip[i].nxt){int top[i].to;dfs(to);op[x]op[to]^1;} return;
}int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();for(int i1;in;i) a[i]read();for(int i2;in;i) addline((int)read(),i);dfs(1);for(int i1;in;i){num[op[i]];if(op[i]) s^a[i];}if(s0){ll ans1ll*num[0]*(num[0]-1)/21ll*num[1]*(num[1]-1)/2;for(int i1;in;i){if(op[i]) mp[a[i]];}for(int i1;in;i){if(!op[i]) ansmp[a[i]];}printf(%lld\n,ans);}else{ll ans(0);for(int i1;in;i){if(op[i]) mp[a[i]^s];}for(int i1;in;i){if(!op[i]) ansmp[a[i]];}printf(%lld\n,ans);}return 0;
}
