ABC050

[ABC050B] Contest with Drinks Easy

题面翻译

joisino 小姐姐即将参加某个编程比赛的决赛。在这个比赛中，准备了 \(N\) 个问题，其中从 \(1\) 到 \(N\) 号码。我知道 joisino 小姐姐要解决问题 \(i\)（\(1≤i≤N\)）需要的时间是 \(T_i\) 秒。

另外，在这个比赛中，提供M种不同的饮料，有 \(1\)~\(M\) 的号码。如果喝了饮料 \(i\)（\(1≤i≤M\)） 的话，参赛者的大脑会被给予强烈的刺激，解决问题 \(P_i\) 的时间是 \(X_i\) 秒。问题之间的时间互不 影响。

每名参赛者在比赛开始前可以喝一瓶饮料。小姐姐joisino对于各自的饮料，想知道要解答所有的问题需要多少秒。解决所有问题的时间是解决各个问题的时间的总和。你的工作是为了帮助(取悦)小姐姐写一个程序。

题目描述

joisinoお姉ちゃんは、あるプログラミングコンテストの決勝を控えています。 このコンテストでは、$ N $ 問の問題が用意されており、それらには $ 1～N $ の番号がついています。 joisinoお姉ちゃんは、問題 $ i(1≦i≦N) $ を解くのにかかる時間が $ T_i $ 秒であることを知っています。

また、このコンテストでは、$ M $ 種類のドリンクが提供されており、$ 1～M $ の番号がついています。 そして、ドリンク $ i(1≦i≦M) $ を飲むと、脳が刺激され、問題 $ P_i $ を解くのにかかる時間が $ X_i $ 秒になります。 他の問題を解くのにかかる時間に変化はありません。

コンテスタントは、コンテスト開始前にいずれかのドリンクを $ 1 $ 本だけ飲むことができます。 joisinoお姉ちゃんは、それぞれのドリンクについて、それを飲んだ際に、全ての問題を解くのに何秒必要なのかを知りたくなりました。 全ての問題を解くのに必要な時間とは、それぞれの問題を解くのにかかる時間の合計です。 あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作成することです。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ T_1 $ $ T_2 $ $ ... $ $ T_N $ $ M $ $ P_1 $ $ X_1 $ $ P_2 $ $ X_2 $ $ : $ $ P_M $ $ X_M $

输出格式

それぞれのドリンクについて、それを飲んだ際に全ての問題を解くのに必要な時間を求め、順番に $ 1 $ 行ずつ出力せよ。

样例 #1

样例输入 #1

3
2 1 4
2
1 1
2 3

样例输出 #1

6
9

样例 #2

样例输入 #2

5
7 2 3 8 5
3
4 2
1 7
4 13

样例输出 #2

19
25
30

提示

制約

• 入力は全て整数である
• $ 1≦N≦100 $
• $ 1≦T_i≦10^5 $
• $ 1≦M≦100 $
• $ 1≦P_i≦N $
• $ 1≦X_i≦10^5 $

Sample Explanation 1

一つ目のドリンクを飲んだ場合、それぞれの問題を解くのに要する時間は、$ 1 $ 秒、$ 1 $ 秒、$ 4 $ 秒になります。 なので、それらを合計した $ 6 $ 秒が答えになり、$ 6 $ を出力します。 二つ目のドリンクを飲んだ場合、それぞれの問題を解くのに要する時間は、$ 2 $ 秒、$ 3 $ 秒、$ 4 $ 秒になります。 なので、それらを合計した $ 9 $ 秒が答えになり、$ 9 $ を出力します。

思路

其实求的就是喝下第\(i\)杯饮料后，总时间变为多少。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
int t[110];
int main(){
    ios::sync_with_stdio(false);
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>t[i],sum+=t[i];
    int m;cin>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        cout<<sum-t[x]+y<<"\n";
    }
    return 0;
}

[ABC050C] Lining Up

题面翻译

有编号为1-N号的N个人，他们都记得“自己左边排队的人数和自己右边排队的人数之差的绝对值”，根据他们的报告，给你i的「自己的左排列的人数和自己的右排列的人数的差的绝对值」Ai。 请根据他们的报告，求出原来的排列方法有几种。但是，因为答案有时候会变得很大，请对10^9+7取模 。另外，他们的报告可能有错误，没有可能的排列方法，此时请输出0。

范围： \[ 1≦N≦10^5; 0≦Ai≦N−1. \]

题目描述

$ 1～N $ までの番号がついた、$ N $ 人の人がいます。 彼らは昨日、ある順番で左右一列に並んでいましたが、今日になってその並び方が分からなくなってしまいました。 しかし、彼らは全員、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」を覚えています。 彼らの報告によると、人 $ i $ の、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」は $ A_i $ です。

彼らの報告を元に、元の並び方が何通りあり得るかを求めてください。 ただし、答えは非常に大きくなることがあるので、$ 10^9+7 $ で割った余りを出力してください。 また、彼らの報告が間違っており、ありうる並び方がないこともありえます。 その際は $ 0 $ を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

输出格式

元の並び順としてありうるものが何通りあるか求め、$ 10^9+7 $ で割った余りを出力せよ。

样例 #1

样例输入 #1

5
2 4 4 0 2

样例输出 #1

4

样例 #2

样例输入 #2

7
6 4 0 2 4 0 2

样例输出 #2

0

样例 #3

样例输入 #3

8
7 5 1 1 7 3 5 3

样例输出 #3

16

提示

制約

• $ 1≦N≦10^5 $
• $ 0≦A_i≦N-1 $

Sample Explanation 1

ありうる並び方は、人の番号で書くと、 - $ 2,1,4,5,3 $ - $ 2,5,4,1,3 $ - $ 3,1,4,5,2 $ - $ 3,5,4,1,2 $ の $ 4 $ 通りです。

Sample Explanation 2

どのような並び方でも、報告と矛盾するので、$ 0 $ が答えになります。

思路

当初WA了好多发，不是忘记取模，就是WA了一个点qwq。

思路不难想，不过要注意分奇偶讨论。

注意到分布的值\(A_i\)应该具有对称性，所以对于每一个\(A_i\)值，它可能的个数就只能是0或2（除了为奇数情况时，0值只有一个，其他情况没有0值）。

所以我们只需要分奇偶讨论，然后判断即可。

注意到范围很大，所以可以用快速幂优化一下（我也不知道没有快速幂会不会喜提\(TLE\)）。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
int b[MAXN];
struct node{
    int num;
    int id;
}a[MAXN];
bool cmp(node a,node b){
    return a.num>b.num;
}
ll qpower(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].num;
        b[a[i].num]++;
    }
    if(n&1){
        for(int i=0;i<=n-1;i+=2){
            if(b[0]!=1){
                cout<<0;
                return 0;
            }
            if(i!=0&&b[i]!=2){
                cout<<0;
                return 0;
            }
        }
    }
    else{
        for(int i=1;i<=n-1;i+=2){
            if(b[i]!=2){
                cout<<0;
                return 0;
            }
        }
    }
    ll ans=qpower(2,n/2);
    cout<<ans;
    return 0;
}

[ABC050D] Xor Sum

题面翻译

题目描述

给出正整数\(N\).

求出整数对\(u\)和\(v\) \((0≤u,v≤N)\)的数目，使得存在两个非负整数\(a\)和\(b\)满足\(a\ xor\ b = u\)和\(a\ +\ b= v\)。这里，\(xor\)表示按位异或。 要求对答案取模\(10^9 + 7\)。

输入输出格式

输入格式

一个正整数\(N\)

输出格式

满足条件的\(u,v\)的个数，对\(10^9+7\)取模

数据范围：

\(N<=10^{18}\)

题目描述

正の整数 $ N $ が与えられます。 $ 2 $ つの整数 $ u,v(0≦u,v≦N) $ であって、ある非負整数 $ a,b $ が存在して、$ a $ $ xor $ $ b=u \(、\) a+b=v $ となるようなものが何通りあるかを求めてください。 ここで、$ xor $ はビットごとの排他的論理和を表します。 なお、答えは非常に大きくなることがあるので、$ 10^9+7 $ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

ありうる $ 2 $ 数の組が何通りあるかを求め、$ 10^9+7 $ で割った余りを出力せよ。

样例 #1

样例输入 #1

3

样例输出 #1

5

样例 #2

样例输入 #2

1422

样例输出 #2

52277

样例 #3

样例输入 #3

1000000000000000000

样例输出 #3

787014179

提示

制約

• $ 1≦N≦10^{18} $

Sample Explanation 1

$ u,v $ としてありうるものは、以下の $ 5 $ 通りです。 - $ u=0,v=0 $（ $ a=0,b=0 $ とすると、$ 0 $ $ xor $ $ 0=0 \(、\) 0+0=0 $ となります。） - $ u=0,v=2 $（ $ a=1,b=1 $ とすると、$ 1 $ $ xor $ $ 1=0 \(、\) 1+1=2 $ となります。） - $ u=1,v=1 $（ $ a=1,b=0 $ とすると、$ 1 $ $ xor $ $ 0=1 \(、\) 1+0=1 $ となります。） - $ u=2,v=2 $（ $ a=2,b=0 $ とすると、$ 2 $ $ xor $ $ 0=2 \(、\) 2+0=2 $ となります。） - $ u=3,v=3 $（ $ a=3,b=0 $ とすると、$ 3 $ $ xor $ $ 0=3 \(、\) 3+0=3 $ となります。）

思路

[题解 ARC066] B - 洛谷专栏 (luogu.com.cn)

暂时先不写思路了，帮舍友配博客去了。可以先看看上面的文章，大佬讲得很好。

---

补思路

一开始的想法是\(v\)可能与\(u\)相同，或者比\(u\)多出一位（这里是二进制位），所以肯定比\(u\)多出\(2^{n+1}\)（假设\(u\)原来有\(n\)位），然后想办法枚举，发现好像不行？也许以后尝试实现一下

下面的思路是大佬的：

考虑 \[ a+b=((a\ and\ b)<<1)+(a\ xor\ b) \] $

这个式子的意义在于，后半部分是因为异或运算是二进制下不进位的加法，前半部分则是在描述二进制下的进位。反正无论怎么样，我们可以轻松得到\(a+b\geq a\ xor b\)这样的结论。

那么如果由于\(u<v\)，所以如果\(v\)不越界那么\(u\)一定不越界。于是考虑按\(v\)进行\(dp\)。具体的，考虑状态\(f_{i,j}\)表示考虑了\(a\)和\(b\)二进制下的前\(i\)位，当前\(v=a+b=j\)的方案数。

考虑如何转移。对于\(a\)和\(b\)而言，第\(i\)位有三种情况，\((0,0),(0,1),(1,1)\)。那么也就是假设原来的和为\(j'\)，和当前的和\(j\)可能有以下关系：

1、\(2*(j'+1)=j\)对应着都补一位1。

2、\(2*j'=j\)对应着都补一位0 。

3、\(j'+(j'+1)=j\)对应着一个补1一个补0 。

那么也就是 \[ f_{i,j}=f_{i-1,\lfloor \frac{j}{2}\rfloor}+f_{i-1,\lfloor \frac{(j-1)}{2}\rfloor}+f_{i-1,\lfloor{\frac{(j-2)}{2}\rfloor}} \]

考虑把第一维压掉之后，就是另一篇题解的那种做法了。

（下面的代码就是优化的）

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
//注意范围为10^18，所以用map
map<ll,ll> m;
ll qpower(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}
ll solve(ll x){
    if(m[x])return m[x];
    return m[x]=(solve(x/2)+solve((x-1)/2)+solve((x-2)/2))%mod;
}
int main(){
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    m[0]=1;
    m[1]=2;
    ll ans=solve(n);
    cout<<ans;
    return 0;
}