毫无悬念地被大一爷锤爆了，一道难题也不会，摸了个第十
A - Rapport Test
线段树，主席树
B - Carving
二分
二分内切球半径(r)，使得球心((r,r,r))到平面(frac{x}{a}+frac{y}{b}+frac{z}{c}=1)的距离为(r)
#include <cstdio>
#include <cmath>
using namespace std;
int a,b,c;
double l,r,mid,v,k1,k2,k3,eps=1e-9;
int main(){
scanf("%d%d%d",&a,&b,&c);
l=0,r=(double)a*b*c/(a*b+b*c+a*c);
k1=a*b+b*c+a*c;
k2=a*b*c;
k3=sqrt(pow(a*b,2)+pow(b*c,2)+pow(a*c,2));
while (r-l>eps){
mid=(r+l)/2;
if ((k2-mid*k1)/k3>mid)
l=mid;else r=mid;
}
v=4.0/3.0*M_PI*pow(l,3);
printf("%.2lf",v);
}
C - Rather Easy Problem
中国剩余定理
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll ex_gcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;y=0;
return a;
}
ll ans=ex_gcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
ll modeqset(ll *a,ll *b,ll n){
ll i,d,c,x,y,t;
for(i=1;i<n;i++){
c=b[i]-b[i-1];
d=ex_gcd(a[i-1],a[i],x,y);
if(c%d) return -1;
t=a[i]/d;
x=(x*(c/d)%t+t)%t;
b[i]=x*a[i-1]+b[i-1];
a[i]=a[i-1]*(a[i]/d);
}
return b[n-1];
}
int main(){
ll a[30],b[30],m,tmp,flag,i,n,lcm=1,num;
lcm=1;
scanf("%lld%lld",&n,&m);
for(i=0;i<m;i++){
scanf("%lld",&a[i]);
lcm=lcm/(gcd(lcm,a[i]))*a[i];
}
for(i=0;i<m;i++) scanf("%lld",&b[i]);
ll res=modeqset(a,b,m);
if(res==-1|| res>n){
printf("0
");
}else{
num=(n-res)/lcm+1;
if(res==0) num--;
printf("%lld
",num);
}
return 0;
}
D - Nearest Shelter
并查集，离散化
考虑到实际上只有(m)个点是有意义的，所以可以先对坐标进行离散化
再用并查集进行路径压缩，从而加快查询速度
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,m,op,pos,fa[N],tmp[N],dis[N];
struct L{
int op,pos;
}l[N];
int find(int x){
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
int getid(int x){
return lower_bound(tmp+1,tmp+m+2,x)-tmp;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m+1;i++) fa[i]=i;
for (int i=1;i<=m;i++){
scanf("%d%d",&l[i].op,&l[i].pos);
tmp[i]=l[i].pos;
}
tmp[m+1]=n+1;
sort(tmp+1,tmp+m+2);
for (int i=1;i<=m;i++){
int id=getid(l[i].pos),nextid=getid(l[i].pos+1);
if (l[i].op==1){
if (tmp[nextid]==l[i].pos+1)
fa[id]=nextid;
dis[id]=1;
}else{
int x=find(id);
if (x==m+1){
printf("-1
");
}else{
if (dis[x])
printf("%d
",tmp[x]+1);
else
printf("%d
",tmp[x]);
}
}
}
}
E - Didn't I Say to Make My Abilities Average in the Next Life?!
线段树
开两个线段树，一个维护区间最大值，另一个维护区间最小值
取查询结果的均值即可
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1e5;
int n,m,a,op,cnt=0,q[N],qcnt=0;
struct MaxSTree{
struct P{
int l,r,v,tag;
}t[4*N];
int v[N];
int build(int x,int l,int r){
t[x].l=l,t[x].r=r,t[x].tag=0;
if (l==r) return t[x].v=v[l];
int mid=(l+r)/2;
return t[x].v=max(build(x*2,l,mid),build(x*2+1,mid+1,r));
}
void pushdown(int x){
if (!t[x].tag) return;
t[x*2].v+=t[x].tag;
t[x*2+1].v+=t[x].tag;
t[x*2].tag+=t[x].tag;
t[x*2+1].tag+=t[x].tag;
t[x].tag=0;
}
int add(int x,int l,int r,int v){
if (l==t[x].l&&r==t[x].r){t[x].tag+=v;return t[x].v+=v;}
pushdown(x);
int mid=(t[x].l+t[x].r)/2;
if (r<=mid) return t[x].v=max(t[x*2+1].v,add(x*2,l,r,v));
else if (l>=mid+1) return t[x].v=max(t[x*2].v,add(x*2+1,l,r,v));
else return t[x].v=max(add(x*2,l,mid,v),add(x*2+1,mid+1,r,v));
}
int query(int x,int l,int r){
if (l==t[x].l&&r==t[x].r) return t[x].v;
pushdown(x);
int mid=(t[x].l+t[x].r)/2;
if (r<=mid) return query(x*2,l,r);
else if (l>=mid+1) return query(x*2+1,l,r);
else return max(query(x*2,l,mid),query(x*2+1,mid+1,r));
}
}st1,st2;
int main(){
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++){
scanf("%d",&op);
if (op==1){
scanf("%d",&a);
st1.v[cnt]=a;
st2.v[cnt]=-a;
cnt++;
}else{
q[qcnt]=cnt;
qcnt++;
}
}
st1.build(1,0,cnt-1);
st2.build(1,0,cnt-1);
for (int i=0;i<qcnt;i++){
double ans=(double)(st1.query(1,max(q[i]-m,0),q[i]-1)-st2.query(1,max(q[i]-m,0),q[i]-1))/2;
printf("%.1lf
",ans);
}
}
F - Fatdog 和他的拓扑排列
找规律，分类讨论
G - Fatdog Wants to Buy Games
并查集
容易看出答案是连通块个数减一
另外需要考虑没有任何人玩过游戏的特殊情况，这时答案是总人数
#include <cstdio>
const int N=2e5+1;
int n,m,k,u,v,fa[N],vis[N],ans=0;
int find(int x){
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n+m;i++) fa[i]=i;
for (int i=1;i<=k;i++){
scanf("%d%d",&u,&v);
int fx=find(u),fy=find(n+v);
if (fx!=fy) fa[fx]=fy;
}
for (int i=1;i<=n;i++){
int fx=find(i);
if (!vis[fx]){
vis[fx]=1;
ans++;
}
}
if (k==0)
printf("%d",n);
else
printf("%d",ans-1);
}
H - Moca 酱果然是天才
概率DP
I - 致十年以后的我，现在的你猜的是什么数？
阶乘
容易看出最优的询问方式是依次询问二进制的每一位，所以答案是(n)的排列数
当(n)超过(10^6+3)时，因为计算过程中有模数因子，所以答案为(0)
#include <cstdio>
#define ll long long
const ll M=1e6+3;
ll n,ans=1,k=1;
int main(){
scanf("%lld",&n);
if (n>=M)
ans=0;
else
for (ll i=1;i<=n;i++) ans=ans*i%M;
printf("%lld",ans);
}
J - Kanade Loves Symmetry
递归，树状数组
依次处理从左到右的每个字符，只需要将同一种字符中最靠右侧的一个移动到与之相对称位置即可
如果当前处理的字符没有剩余可以与之配对的相同字符，则交换顺序从右向左处理
需要使用树状数组来维护每个元素在移动后的正确位置
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+1;
deque<int> q[26];
string s;
ll len,cnt[26],pd=0,ans,vis[N],t[N],l,r;
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
while(x<=len+1){
t[x]+=v;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
int main(){
cin>>s;
len=s.length();
l=0;r=len-1;
for (ll i=0;i<len;i++){
ll x=s[i]-'a';
q[x].push_back(i);
cnt[x]++;
}
for (ll i=0;i<26;i++){
if (cnt[i]%2==1) pd++;
}
if (pd>1){
printf("Impossible");
return 0;
}
for (ll i=0;i<len/2;i++){
while (vis[l]) l++;
while (vis[r]) r--;
ll lnow=i;
ll rnow=len-i-1;
ll x=s[l]-'a';
if (q[x].size()>=2){
ll mov=q[x].back();
ll movnow=mov-query(mov+1);
ans+=rnow-movnow;
q[x].pop_front();q[x].pop_back();
add(mov+1,1);
vis[l]=1;vis[mov]=1;
}else{
x=s[r]-'a';
ll mov=q[x].front();
ll movnow=mov-query(mov+1);
ans+=movnow-lnow;
q[x].pop_front();q[x].pop_back();
add(l+1,-1);add(mov+1,1);
vis[r]=1;vis[mov]=1;
}
}
printf("%lld",ans);
}
K - Senpai and Pascal
找规律
从第一个二进制不同的位开始依次填写(1)即可
#include <cstdio>
#define ll long long
ll a,b,c;
ll l[63],r[63],x[63];
int main(){
scanf("%lld%lld",&a,&b);
for (ll i=0;i<63;i++) if (a&(1LL<<i)) l[i]++;
for (ll i=0;i<63;i++) if (b&(1LL<<i)) r[i]++;
for (ll i=62;i>=0;i--){
if (l[i]==r[i]){
c+=(l[i]<<i);
}else{
c+=(1LL<<(i+1))-1;
break;
}
}
printf("%lld
",c);
}
L - UESTCPC Finals 2077
最大值
排除掉第一名做过的题目后在剩余的题目中找通过人数最多的即可
#include <bits/stdc++.h>
using namespace std;
int n,a[13],b[13],ans,maxx=0;
string f;
int main(){
cin>>n;
cin>>f;
for (int i=0;i<n;i++) b[f[i]-'A']=1;
for (int i=0;i<13;i++) cin>>a[i];
for (int i=0;i<13;i++){
if (a[i]>maxx&&!b[i]){
ans=i;
maxx=a[i];
}
}
printf("%c
",'A'+ans);
}
M - 查理不冲浪！
自动机
手写自动机进行模式匹配
#include <bits/stdc++.h>
using namespace std;
const int R=10,C=1e5;
int r,c;
char a[R][C],ans[C];
void dfs(int y,int x){
a[y][x]='.';
if (y-1>=0&&a[y-1][x]=='o') dfs(y-1,x);
if (y+1<r&&a[y+1][x]=='o') dfs(y+1,x);
if (x-1>=0&&a[y][x-1]=='o') dfs(y,x-1);
if (x+1<c&&a[y][x+1]=='o') dfs(y,x+1);
}
int main(){
scanf("%d%d",&r,&c);
for (int i=0;i<r;i++){
string f;
cin>>f;
for (int j=0;j<c;j++)
a[i][j]=f[j];
}
for (int i=0;i<c;i++){
for (int j=0;j<r;j++){
if (a[j][i]=='o'){
if (a[j+1][i]=='o'&&a[j+2][i]=='o'&&a[j+3][i]=='o'&&a[j+4][i]=='o'){
if (a[j][i+1]=='.'){
ans[i]='1';
}
else if (a[j+2][i+1]=='.'){
ans[i+1]='0';
}
else if (a[j+1][i+2]=='o'){
ans[i+1]='8';
}else{
ans[i+1]='6';
}
}
else if (a[j][i+1]=='.'){
ans[i+1]='4';
}
else if (a[j+2][i+1]=='.'){
ans[i+1]='7';
}
else if (a[j+1][i]=='.'&&a[j+2][i]=='o'&&a[j+3][i]=='o'&&a[j+4][i]=='o'){
ans[i+1]='2';
}
else if (a[j+1][i]=='.'&&a[j+2][i]=='o'&&a[j+3][i]=='.'&&a[j+4][i]=='o'){
ans[i+1]='3';
}
else if (a[j+1][i]=='o'&&a[j+2][i]=='o'&&a[j+3][i]=='.'&&a[j+4][i]=='o'){
if (a[j+1][i+2]=='o'){
ans[i+1]='9';
}else{
ans[i+1]='5';
}
}
dfs(j,i);
}
}
if (ans[i]) printf("%c",ans[i]);
}
}
N - The Journey of Elaina
DFS序，树状数组
参考DFS序七个经典问题，本题目对应的问题是单点修改、子树和查询
#include <cstdio>
const int N=1e5+1;
int n,f[N],p[N],q,op,c,w,t[N],cnt=0,idx1[N],idx2[N];
int sz,head[N],vis[N];
struct E{
int next,to;
}e[N*2];
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
while(x<=n){
t[x]+=v;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
void insert(int a,int b){
sz++;
e[sz].next=head[a];
head[a]=sz;
e[sz].to=b;
}
void dfs(int x){
vis[x]=1;
idx1[x]=++cnt;
for (int i=head[x];i;i=e[i].next){
int v=e[i].to;
if (!vis[v]) dfs(v);
}
idx2[x]=cnt;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&f[i]);
for (int i=2;i<=n;i++){
scanf("%d",&p[i]);
insert(i,p[i]);
insert(p[i],i);
}
dfs(1);
for (int i=1;i<=n;i++){
add(idx1[i],f[i]);
}
scanf("%d",&q);
for (int i=1;i<=q;i++){
scanf("%d",&op);
if (op==1){
scanf("%d%d",&c,&w);
add(idx1[c],w-f[c]);
f[c]=w;
}else{
scanf("%d",&c);
printf("%d
",sum(idx2[c])-sum(idx1[c]-1));
}
}
}
O - Fatdog's True Love
二分，容斥
P - UNIX 时间戳
差分约束