ABC044

要开始加训了！！！不然太菜找不到队友了┭┮﹏┭┮

[ABC044A] 高橋君とホテルイージー

题面翻译

有一家酒店，这家酒店住宿费的收取规则如下

前K晚每晚X元

从K+1晚开始每晚Y元

高橋老弟要在这里连续住N晚，问他的住宿费合计为多少元

输入格式

第一行，N

第二行，K

第三行，X

第四行，Y

输出格式

一行，住宿总费用

题目描述

$ 1 $ 軒のホテルがあります。このホテルの宿泊費は、次のようになっています。

最初の $ K $ 泊までは、$ 1 $ 泊あたり $ X $ 円

$ K+1 $ 泊目以降は、$ 1 $ 泊あたり $ Y $ 円

高橋君は、このホテルに $ N $ 泊連続で宿泊することにしました。高橋君の宿泊費は合計で何円になるか求めてください。

输入格式

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

$ N $ $ K $ $ X $ $ Y $

输出格式

高橋君の宿泊費の合計金額を表す整数を出力せよ。

样例 #1

样例输入 #1
5
3
10000
9000
样例输出 #1
48000
样例 #2

样例输入 #2
2
3
10000
9000
样例输出 #2
20000
提示

制約

$ 1 N, K 10000 $

$ 1 Y $

$ N,,K,,X,,Y $ はいずれも整数である

Sample Explanation 1

宿泊費は次のようになります。 - $ 1 $ 泊目は $ 10000 $ 円 - $ 2 $ 泊目は $ 10000 $ 円 - $ 3 $ 泊目は $ 10000 $ 円 - $ 4 $ 泊目は $ 9000 $ 円 - $ 5 $ 泊目は $ 9000 $ 円したがって、合計は $ 48000 $ 円です。

思路

直接模拟即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int a[110];
map<char,int> m;
bool palindrome(ll n) {//判定回文，不懂请参考数字反转
    ll sum = 0;
    ll k = n;
    while (n != 0) {
        sum = sum * 10 + n % 10;
        n /= 10;
    }
    if (sum == k)//判断是否回文
        return 1;
    else
        return 0;
}
int main(){
    ios::sync_with_stdio(0);
    int n,k,x,y;cin>>n>>k>>x>>y;
    if(n<=k){
        cout<<n*x;
    }
    else{
        ll ans=0;
        ans+=k*x+(n-k)*y;
        cout<<ans;
    }
    return 0;
}

[ABC044B] 美しい文字列

题面翻译

输入一个字符串，判断每个字母出现的次数是否都为偶数

如果是，输出“Yes”，否则输出“No”

题目描述

$ w $ を、英小文字のみからなる文字列とします。 $ w $ が以下の条件を満たすならば、$ w $ を美しい文字列と呼ぶことにします。

どの英小文字も、$ w $ 中に偶数回出現する。

文字列 $ w $ が与えられます。$ w $ が美しい文字列かどうか判定してください。

输入格式

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

$ w $

输出格式

$ w $ が美しい文字列ならば Yes を、それ以外の場合は No を出力せよ。

样例 #1

样例输入 #1
abaccaba
样例输出 #1
Yes
样例 #2

样例输入 #2
hthth
样例输出 #2
No
提示

制約

$ 1 |w| 100 $

$ w $ は英小文字 (a-z) のみからなる文字列である

Sample Explanation 1

a が $ 4 $ 回、b が $ 2 $ 回、c が $ 2 $ 回、それ以外の英小文字が $ 0 $ 回出現します。

思路

开个桶，直接统计即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
map<char,int> m;
bool palindrome(ll n) {//判定回文，不懂请参考数字反转
    ll sum = 0;
    ll k = n;
    while (n != 0) {
        sum = sum * 10 + n % 10;
        n /= 10;
    }
    if (sum == k)//判断是否回文
        return 1;
    else
        return 0;
}
int main(){
    ios::sync_with_stdio(0);
    string s;cin>>s;
    for(int i=0;i<s.length();i++){
        m[s[i]]++;
    }
    for(char i='a';i<='z';i++){
        if(m[i]%2){
            cout<<"No\n";
            return 0;
        }
    }
    cout<<"Yes\n";
    return 0;
}

[ABC044C] 高橋君とカード

题面翻译

高桥有n张卡。在i(1≤i≤n)的第一个磁卡上，卡上面写着整数x_i。

高桥从这些卡片中挑选1张以上，想把选择的卡片上写的整数的平均数变成等于A的数。问有几种方案。

读入：第一行读入N,A；接下来一行读入N个数

输出：一个数，记得加回车

感谢@STEPHEN_ 提供的翻译

题目描述

高橋君は、$ N $ 枚のカードを持っています。 $ i , (1 i N) $ 番目のカードには、整数 $ x_i $ が書かれています。高橋君は、これらのカードの中から $ 1 $ 枚以上を選び、選んだカードに書かれた整数の平均をちょうど $ A $ にしたいと考えています。そのようなカードの選び方が何通りあるか求めてください。

输入格式

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

$ N $ $ A $ $ x_1 $ $ x_2 $ $ ... $ $ x_N $

输出格式

書かれた整数の平均がちょうど $ A $ となるようなカードの選び方の総数を出力せよ。

样例 #1

样例输入 #1
4 8
7 9 8 9
样例输出 #1
5
样例 #2

样例输入 #2
3 8
6 6 9
样例输出 #2
0
样例 #3

样例输入 #3
8 5
3 6 2 8 7 6 5 9
样例输出 #3
19
样例 #4

样例输入 #4
33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
样例输出 #4
8589934591
提示

制約

$ 1  N  50 $

$ 1  A  50 $

$ 1  x_i  50 $

$ N,,A,,x_i $ はいずれも整数である

部分点

$ 1  N  16 $ を満たすデータセットに正解した場合は、$ 200 $ 点が与えられる。

Sample Explanation 1

- 平均が $ 8 $ となるカードの選び方は、以下の $ 5 $ 通りです。 - $ 3 $ 枚目のカードのみを選ぶ。 - $ 1 $ 枚目と $ 2 $ 枚目のカードを選ぶ。 - $ 1 $ 枚目と $ 4 $ 枚目のカードを選ぶ。 - $ 1 $ 枚目、$ 2 $ 枚目および $ 3 $ 枚目のカードを選ぶ。 - $ 1 $ 枚目、$ 3 $ 枚目および $ 4 $ 枚目のカードを選ぶ。

Sample Explanation 4

- 答えは $ 32 $ ビット整数型に収まらない場合があります。

思路

转载自AT2037 题解 - 洛谷专栏 (luogu.com.cn)

计数型01背包。

一开始想的是只写$f_{j}$，表示的是和为$j$的方法数。

但是最后发现不行，因为有可能最后可能不同的组合组成的数为$j$，所以得多加一个维度$i$，表示的是取了$i$个数

所以状态中存了两个值：$f_{i,j}$表示取了$i$个数，和为$j$的方法数。

这样转移方程为：$f_{i,j}=f_{i,j}+f_{i-1,j-a_k}$，$i-1$是这个数还没取，也就是少取了一个，$j-a_k$表示当前这个和减去现在的这个值，也就是之前的和。

注意就是枚举$i$和$j$时要反着枚举，初始化$f[0][0]=1$，开$long\ long$。

注意平均值不一定是整数哦。

#include<iostream>
using namespace std;
int a[55];
long long f[55][2505];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[0][0]=1;//设初值。
    for(int i=1;i<=n;i++)
        for(int j=2500;j>=a[i];j--)
            for(int k=n;k>=1;k--)
                f[k][j]+=f[k-1][j-a[i]];
  		//注意这两重循环是反着的，否则会从已经改过的值转移来。
    long long sum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=2500;j++)
            sum+=(j*1.0/i==double(m))*f[i][j];
  	//如果平均值等于 m 就将 sum 加上 f[i][j]。
    cout<<sum<<endl;//AT 加换行。
    return 0;
}

自己的实现

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
ll a[55],f[55][2510];
int main(){
    ios::sync_with_stdio(0);
    int n,A;cin>>n>>A;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=2500;j>=a[i];j--){
            for(int k=n;k>=1;k--){
                f[k][j]+=f[k-1][j-a[i]];
            }
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2500;j++){
            if((j*1.0/i)==(double)A)sum+=f[i][j];
        }
    }
    cout<<sum;
    return 0;
}

[ABC044D] 桁和

题面翻译
题目描述

对于2以上的整数b和一个1以上的整数n，函数f(b,n)的定义如下：

1.若n<b,f(b，n)=n;

2.若n>=b,f(b,n)=f(b,floor(n/b))+(n%b).

说白了就是即n在b进制下各位数的和 举个例子：

f(10,87654)=8+7+6+5+4=30

f(100,87654)=8+76+54=138

设函数f(b,n)的值为s；

输入输出格式

输入格式

输入包含两个数，代表n,s的值

输出格式

输出包含1个数，是b的值，如果找不到符合要求的b值，则输出-1
注：此为Over_The_Best翻译，但他被禁言了，由我代发

题目描述

$ 2 $ 以上の整数 $ b $ および $ 1 $ 以上の整数 $ n $ に対し、関数 $ f(b,n) $ を次のように定義します。

$ n < b $ のとき $ f(b,n) = n $

$ n b $ のとき $ f(b,n) = f(b,,{}(n / b)) + (n {} b) $

ここで、$ {}(n / b) $ は $ n / b $ を超えない最大の整数を、 $ n {} b $ は $ n $ を $ b $ で割った余りを表します。

直感的に言えば、$ f(b,n) $ は、$ n $ を $ b $ 進表記したときの各桁の和となります。例えば、

$ f(10,,87654)=8+7+6+5+4=30 $

$ f(100,,87654)=8+76+54=138 $

などとなります。

整数 $ n $ と $ s $ が与えられます。 $ f(b,n)=s $ を満たすような $ 2 $ 以上の整数 $ b $ が存在するか判定してください。さらに、そのような $ b $ が存在するならば、その最小値を求めてください。

输入格式

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

$ n $ $ s $

输出格式

$ f(b,n)=s $ を満たす $ 2 $ 以上の整数 $ b $ が存在するならば、そのような $ b $ の最小値を出力せよ。そのような $ b $ が存在しないならば、代わりに -1 を出力せよ。

样例 #1

样例输入 #1
87654
30
样例输出 #1
10
样例 #2

样例输入 #2
87654
138
样例输出 #2
100
样例 #3

样例输入 #3
87654
45678
样例输出 #3
-1
样例 #4

样例输入 #4
31415926535
1
样例输出 #4
31415926535
样例 #5

样例输入 #5
1
31415926535
样例输出 #5
-1
提示

制約

$ 1 n 10^{11} $

$ 1 s 10^{11} $

$ n,,s $ はいずれも整数である

思路

题解区都是一堆奇怪的显然，莫名其妙的就是$O(\sqrt{n})$的时间复杂度。幸好在下面翻到一篇好文章，这里是原文链接：AT2038 - 洛谷专栏 (luogu.com.cn)

其实是一道数学题

不妨设$n=a_0+a_1b+a_2b^2+······$，则$s=a_0+a_1+a_2+······$。

先考虑特殊情况 :

1、$n=s$，则$b=n+1$

2、$n<s$，则无解。

我们用$n$减去$s$：

$n-s=a_1(b-1)+a_2(b^2-1)+a_3(b^3-1)+······$。

容易知道，$b^n-1=(b-1)(b^{n-1}+b^{n-2}+b^{n-3}+······+1)$，所以说 , 右式可以提出$b-1$。

显然：$(b-1)|n-s$，那么$b$可能的取值范围就缩成了$\sqrt{n}$数量级，接下来直接调用函数，暴力枚举即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const int mod=1e9+7;
ll n,s;
ll f(ll b,ll n){
    if(n<b){
        return n;
    }
    return f(b,n/b)+n%b;
}
bool check(ll b){
    if(f(b,n)==s)return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>s;
    if(n<s){
        cout<<-1;
        return 0;
    }
    if(n==s){
        cout<<n+1;
        return 0;
    }
    ll tot=n-s,ans=1e15;
    //可以结合最基础的素数筛，理解为什么枚举到根号n即可
    for(ll i=1;i<=(ll)sqrt(tot)+1;i++){
        if(tot%i==0){
            //注意是判断两个哦
            if(check(i+1))ans=min(ans,i+1);
            if(check(tot/i+1))ans=min(ans,tot/i+1);
        }
    }
    if(ans==1e15)cout<<-1;
    else cout<<ans;
    return 0;
}