脚本宝典收集整理的这篇文章主要介绍了2021-2022 ACM-ICPC Brazil Subregional Programming Contest，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题意：有一个长度为(n)的(B)进制数，问你能否减小某一位上的数，使得其可以整除(B+1)，输出修改的位置和修改后的数，如果不能满足条件输出(-1,-1)，不用修改则输出(0,0).
题解：假设原数在十进制下的数为(N)，那么有(Nequiv rmod (B+1))，修改后的新数为$N'equiv0 mod (B+1) (，所以要满足)N-requiv 0mod (B+1)(，假设我们修改第)i(个位置上的数)a_i(,得到新位置上的数为)c_i(，那么有)(a_i-c_i)b^iequiv rmod (B+1)(，)a_i-c_iequiv rb^{-i}mod (B+1)(，而)a_i-c_i(表示修改后的差值，显然差值的范围是)[1,a_i](，那么只要)r*b^{-i}le a_i$就满足条件，直接输出即可，记得特判不需要修改的情况。这里采取的是扩欧法求逆元。
代码:
#include <bITs/stdc++.h>
#define ll long long
#define fi First
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define PEr(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
ll b,l;
ll d[N];
ll x,y;
ll sum[N],inv[N];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll x_,y_;
ll d=exgcd(b,a%b,x_,y_);
x=y_,y=x_-a/b*y_;
return d;
}
ll cal(ll x){
ll _x,_y;
ll d=exgcd(x,b+1,_x,_y);
return (_x%(b+1)+b+1)%(b+1);
}
int main() {
scanf("%lld %lld",&b,&l);
for(int i=1;i<=l;++i){
scanf("%lld",&d[i]);
}
reverse(d+1,d+1+l);
ll base=1;
for(int i=1;i<=l;++i){
sum[i]=(sum[i-1]+d[i]*base%(b+1))%(b+1);
inv[i]=cal(base);
base=base*b%(b+1);
}
if(sum[l]==0){
puts("0 0");
return 0;
}
ll m=sum[l];
reverse(d+1,d+1+l);
for(int i=1;i<=l;++i){
ll now=m*inv[l-i+1]%(b+1);
if(now<=d[i]){
printf("%d %lldn",i,d[i]-now);
return 0;
}
}
puts("-1 -1");
return 0;
}
题意：有一个双向的电动扶梯，一个乘客从起点到终点需要10s的时间，当没有乘客时，电梯会自动停止，下次开始时可以朝任意方向运行，当电梯朝着某一方向运行时，必须将这个方向的乘客送完才会停止，现在有(n)个乘客，每个乘客都有各自的乘坐起点时间和方向，问你最早什么时候所有乘客都能到达目的地。
题解：一个策略是电梯朝某一方向一直运行直到某一时刻没有乘客乘坐停止，方向相同且起点时刻在这段时间内的乘客都坐上去，停止后，判断哪个方向的乘客起始时刻更近，就朝哪个方向运行，一直这样运行下去，同时注意更新时间即可。
代码：
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
int n;
PII pt[N];
vector<ll> l,r;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d %d",&pt[i].fi,&pt[i].se);
if(pt[i].se==0) l.pb(pt[i].fi);
else r.pb(pt[i].fi);
}
int i=0,j=0;
int dir=pt[1].se;
ll now=0;
bool flag=false;
while(i<(int)l.size() && j<(int)r.size()){
if(dir==0){
if(!flag) now=max(now,l[i]+10);
else{
now=max(now,l[i])+10;
flag=false;
}
i++;
if(i>=(int)l.size()){
dir=1;
flag=true;
continue;
}
if(now<l[i] && r[j]<l[i]){ // change the direction
dir=1;
flag=true;
}
}
else{
if(!flag) now=max(now,r[j]+10);
else{
now=max(now,r[j])+10;
flag=false;
}
j++;
if(j>=(int)r.size()){
dir=0;
flag=true;
continue;
}
if(now<r[j] && l[i]<r[j]) dir=0,flag=true;
}
}
while(i<(int)l.size()){
if(!flag) now=max(now,l[i]+10);
else{
now=max(now,l[i])+10;
flag=false;
}
i++;
}
while(j<(int)r.size()){
if(!flag) now=max(now,r[j]+10);
else{
now=max(now,r[j])+10;
flag=false;
}
j++;
}
printf("%lldn",now);
return 0;
}
对每个颜色的数排序，然后判断即可
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
int n,k;
PII pt[N];
int pos[N];
vector<int> col[N];
queue<int> q[N];
int a[N];
int main() {
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%d %d",&pt[i].fi,&pt[i].se);
pos[i]=pt[i].se;
col[pt[i].se].pb(pt[i].fi);
}
for(int i=1;i<=k;++i){
sort(col[i].begin(),col[i].end());
for(auto w:col[i]) q[i].push(w);
}
bool flag=true;
for(int i=1;i<=n;++i){
int now=pos[i];
a[i]=q[now].front();
q[now].pop();
if(a[i]<a[i-1]){
flag=false;
break;
}
}
if(flag) puts("Y");
else puts("N");
return 0;
}
枚举判断一下区间是否合法即可
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
int t,d,m;
int a[N];
int main() {
scanf("%d %d %d",&t,&d,&;m);
a[1]=0;
for(int i=2;i<=m+1;++i) scanf("%d",&a[i]);
a[m+2]=d;
bool flag=false;
for(int i=1;i<=m+2;++i){
if(a[i]-a[i-1]>=t){
flag=true;
break;
}
}
if(flag) puts("Y");
else puts("N");
return 0;
}
题意：刚开始只有一个编号为(1)的人，他是国王，操作1表示编号为(x)的生了一个孩子，每个人的编号都是唯一的，操作2表示编号为(x)的人g了，假如是国王g了，就要选择新的国王，选举策略是，优先选孩子(一直向下选孩子父亲->儿子->孙子->曾孙子)，如果没孩子，就选最近的兄弟，然后再看兄弟的儿子。。。。,问你每次有人死去的时候，当前的国王是谁
题解：很明显，生一个孩子相当于父节点加了一个儿子结点，选举国王就是一个DFs序，我们先离线将树建好，然后跑一边dfs，把序列求出，之后在用链表进行操作，每次输出头结点对应的值即可。
代码：
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
int n;
int idx;
PII pt[N];
vector<int> Edge[N];
vector<int> v;
int head,e[N],ne[N],pre[N];
int pos[N];
void dfs(int u,int fa){
v.pb(u);
for(auto to:edge[u]){
if(to==fa) continue;
dfs(to,u);
}
return;
}
int main() {
scanf("%d",&n);
idx=1;
for(int i=1;i<=n;++i){
scanf("%d %d",&pt[i].fi,&pt[i].se);
if(pt[i].fi==1) edge[pt[i].se].pb(++idx);
}
dfs(1,-1);
head=0;
ne[head]=1;
for(int i=1;i<=(int)v.size();++i){
e[i]=v[i-1];
ne[i]=i+1;
pre[i]=i-1;
pos[v[i-1]]=i;
}
for(int i=1;i<=n;++i){
if(pt[i].fi==2){
int now=pos[pt[i].se];
pre[ne[now]]=pre[now];
ne[pre[now]]=ne[now];
printf("%dn",e[ne[head]]);
}
}
return 0;
}
主席树求区间中不小于(k)的数出现次数的裸题。。。。
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
int y,n;
int x[N];
int a[N],p[N],f[N];
int root[N],idx;
struct Node{
int l,r;
int cnt;
}tr[N<<4];
int build(int l,int r){
int p=++idx;
if(l==r) return p;
int mid=(l+r)>>1;
build(l,mid),build(mid+1,r);
return p;
}
int update(int p,int l,int r,int x){
int q=++idx;
tr[q]=tr[p];
tr[q].cnt++;
if(l==r) return q;
int mid=(l+r)>>1;
if(x<=mid) tr[q].l=update(tr[p].l,l,mid,x);
else tr[q].r=update(tr[p].r,mid+1,r,x);
return q;
}
int query(int L,int R,int l,int r,int k){
if(l>=k) return tr[R].cnt-tr[L].cnt;
if(l==r) return tr[R].cnt-tr[L].cnt;
int mid=(l+r)>>1;
int res=0;
if(k<=mid) res=query(tr[L].l,tr[R].l,l,mid,k)+query(tr[L].r,tr[R].r,mid+1,r,k);
else res=query(tr[L].r,tr[R].r,mid+1,r,k);
return res;
}
int main() {
scanf("%d %d",&y,&n);
root[0]=build(1,100010);
for(int i=1;i<=y;++i){
scanf("%d",&x[i]);
root[i]=update(root[i-1],1,100010,x[i]);
}
for(int i=1;i<=n;++i){
scanf("%d %d %d",&a[i],&p[i],&f[i]);
if(x[a[i]]>=p[i]) puts("0");
else printf("%dn",query(root[a[i]-1],root[a[i]+f[i]],1,100010,p[i]));
}
return 0;
}
以上是脚本宝典为你收集整理的2021-2022 ACM-ICPC Brazil Subregional Programming Contest全部内容，希望文章能够帮你解决2021-2022 ACM-ICPC Brazil Subregional Programming Contest所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。