[A:划水,B:划水,C:裴蜀定理,D:ST表]Codeforces Round #499(Div.1 VP)题解

好像打了假的Div1……

A

要走 $2n$ 次,每次会耗费 $(m+now)\over a_i$ 的油量( $now$ 表示当前油量,$m$ 固定),问最少带多少油。

因为 $a_i\ge 1$ ,所以带的油越多走的越远,那么二分油就行了……注意精度QAQ。

#include<cstdio>
#include<cmath>
using namespace std;
typedef long double DB;
const int maxn=1000;

int n,m,a[maxn+5],b[maxn+5];

inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-12) return 0;return a<b?-1:1;}
inline bool check(DB now){
    for (int i=1;i<=n;i++){
        if (i>1){
            if (fcmp(now,(m+now)/b[i])<0) return false;
            now-=(m+now)/b[i];
        }
        if (fcmp(now,(m+now)/a[i])<0) return false;
        now-=(m+now)/a[i];
    }
    if (fcmp(now,(m+now)/b[1])<0) return false;return true;
}
int main(){
    freopen("A.in","r",stdin);freopen("A.out","w",stdout);
    scanf("%d%d",&n,&m);DB L=0,R=1e9+1;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    for (DB mid=(L+R)/2;R-L>1e-8;mid=(L+R)/2) check(mid)?R=mid:L=mid;
    if (R>1e9) return puts("-1"),0;
    return printf("%.10f\n",(double)R),0;
}

B

交互题,要猜出一个数,每 $p$ 次会有一次正确回答大于或小于,其余 $p-1$ 次均回答相反的答案即说谎(但如果猜中了一定会正确回答),且刚开始不知道还有几次说谎。在 $60$ 次之内猜出来,要猜的数 $\le 10^9$ ,$p\le 30$ 。

先 $30$ 次猜出还有几次说谎,然后二分要猜的数……代码By Lynstery。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int p[35],m,n,now;
int Get(int x){
  printf("%d\n",x); fflush(stdout);
  int res; scanf("%d",&res);
  return res;
}
int main(){
  scanf("%d%d",&m,&n);
  for(int i=0;i<=n-1;i++){
    int x=Get(1); if(x==0) exit(0);
    if(x==1) p[i]=1; else p[i]=-1; 
  }
  int L=1,R=m; now=n-1;
  while(L<=R){
    int mid=(L+R)>>1;
    int x=Get(mid); if(x==-2) exit(0);
    x*=p[now=(now+1)%n];  
    if(x==0) exit(0);
    if(x==1) L=mid+1; else R=mid-1;
  }
  return 0;
}

C

给出 $\{x_n\}$ 求 $\sum_{i=1}^{n}a_ix_i$ 在 $K$ 进制下最后一位有多少种取值。

挺水的……题目就是要求 $\sum_{i=1}^n a_ix_i\ mod\ K,0\le a_i<K$ 的取值 $y$ 的个数,根据裴蜀定理的推论可以得到 $(a_1,a_2,\cdots,K)|y$ ,所以 $[0,K-1]$ 中 $(a_1,a_2,\cdots,K)$ 的倍数都是可行的取值。代码By Lynstery。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005;
int n,K,res,ans[maxn];
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
int main(){
  scanf("%d%d",&n,&K); res=K;
  for(int i=1;i<=n;i++){
    int x; scanf("%d",&x);
    res=gcd(res,x);
  }
  ans[++ans[0]]=0;
  int now=res; while(now<K) ans[++ans[0]]=now, now+=res;
  printf("%d\n",ans[0]);
  for(int i=1;i<=ans[0]-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[ans[0]]);
  
  return 0;
}

D

给出一个逻辑运算树,每个节点有一个逻辑运算或输入框( $0$ 或 $1$ )以及 $0/1/2$ 个儿子(根据符号定)。问每次只把所有输入框中的一个改成相反的( $0\to 1,1\to 0$ )之后根节点的数。

倍增就行了,记 $ST[x][j][0/1]$ 表示 $x$ 是 $0/1$ ,往上走 $2^j$ 次得到的数,瞎转移。

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=1000000,Log=20;

int ID[256],n,ty[maxn+5],son[maxn+5][2];bool val[maxn+5];
int dep[maxn+5],fa[maxn+5][Log+5];bool ST[maxn+5][Log+5][2];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
void Pre(int x){
    if (ty[x]>3) return;if (son[x][0]) Pre(son[x][0]);if (son[x][1]) Pre(son[x][1]);
    if (ty[x]==0) val[x]=val[son[x][0]]&val[son[x][1]];
    else if (ty[x]==1) val[x]=val[son[x][0]]|val[son[x][1]];
    else if (ty[x]==2) val[x]=val[son[x][0]]^val[son[x][1]];
    else if (ty[x]==3) val[x]=val[son[x][0]]^1;
}
#define Son(x) ((x)==son[pre][1])
void Dfs(int x,int pre=0){
    if (pre){fa[x][0]=pre;dep[x]=dep[pre]+1;
        if (ty[pre]==3) ST[x][0][0]=1,ST[x][0][1]=0;
        else if (ty[pre]==0) ST[x][0][0]=0&val[son[pre][Son(x)^1]],ST[x][0][1]=1&val[son[pre][Son(x)^1]];
        else if (ty[pre]==1) ST[x][0][0]=0|val[son[pre][Son(x)^1]],ST[x][0][1]=1|val[son[pre][Son(x)^1]];
        else if (ty[pre]==2) ST[x][0][0]=0^val[son[pre][Son(x)^1]],ST[x][0][1]=1^val[son[pre][Son(x)^1]];
        for (int j=1;j<=Log;j++) fa[x][j]=fa[fa[x][j-1]][j-1];
        for (int j=1;j<=Log;j++) ST[x][j][0]=ST[fa[x][j-1]][j-1][ST[x][j-1][0]],ST[x][j][1]=ST[fa[x][j-1]][j-1][ST[x][j-1][1]];
    }
    if (son[x][0]) Dfs(son[x][0],x);if (son[x][1]) Dfs(son[x][1],x);
}
inline int getans(int x) {int D=dep[x],ans=val[x]^1;for (int j=Log;~j;j--) if (D>>j&1) ans=ST[x][j][ans],x=fa[x][j];return ans;}
int main(){
    freopen("D.in","r",stdin);freopen("D.out","w",stdout);
    ID['A']=0;ID['O']=1;ID['X']=2;ID['N']=3;ID['I']=4;
    for (int i=(readi(n),1);i<=n;i++){
        char ch=readc();while (ch!='A'&&ch!='O'&&ch!='X'&&ch!='N'&&ch!='I') ch=readc();ty[i]=ID[ch];
        if (ch=='A'||ch=='O'||ch=='X') readi(son[i][0]),readi(son[i][1]);
        else if (ch=='N') readi(son[i][0]); else {int x;readi(x);val[i]=x;}
    }
    Pre(1);Dfs(1);for (int i=1;i<=n;i++) if (ty[i]>3) putchar(getans(i)+48);return 0;
}

本文链接:https://zigzagk.top/2018/08/04/CFR499D1
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。