AtCoder Regular Contest 113训练赛(暴力,快速幂,贪心)

ARC 113

传送门

A. A×B×C

https://atcoder.jp/contests/arc113/tasks/arc113_a

题意

给定一个正整数K,求出正整数排列(A,B,C),使A×B×C ≤ K,的组合个数。

思路

暴力,枚举A、B,求C的个数。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
int k;

int main(){
     
    IOS;
    cin >> k;
    ll res = 0;
    for(int c = 1;c <= k;c++){
     
        int ab = 0;
        ab = k / c;
        for(int a = 1;a <= ab;a++){
     
            res += ab / a;
        }
    }
    cout << res << endl;
    system("pause");
    return 0;
}

B.A ^ B ^C

https://atcoder.jp/contests/arc113/tasks/arc113_b

题意

给定三个数A,B,C,求出 a b c a^{b^c} abc的个位上的数。

思路

①由于我们只需求解个位上数,所以A的个位以上的数对结果无影响,所以我们对A取余。
②找规律,我们发现0-9中每个数的n次方的个位上的数是具有规律性的,结果如下:AtCoder Regular Contest 113训练赛(暴力,快速幂,贪心)_第1张图片
③利用快速幂计算 b c b^c bc对a所在周期取余的结果
④在记录a的n次幂的个位的数组中输出结果。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
int abc[10][5];

ll pm(ll b,ll c,ll mod){
     
    ll res = 1;
    while(c){
     
        if(c & 1){
     
            (res *= b)%= mod;
        }
        c >>= 1;
        (b*=b)%= mod;
    }
    return res;
}


int main(){
     
    IOS;
    int a,b,c;
    abc[2][0] = 6;abc[2][1] = 2;abc[2][2] = 4;abc[2][3] = 8;
    abc[3][0] = 1;abc[3][1] = 3;abc[3][2] = 9;abc[3][3] = 7;
    abc[4][0] = 6;abc[4][1] = 4;
    abc[7][0] = 1;abc[7][1] = 7;abc[7][2] = 9;abc[7][3] = 3;
    abc[8][0] = 6;abc[8][1] = 8;abc[8][2] = 4;abc[8][3] = 2;
    abc[9][0] = 1;abc[9][1] = 9;
    cin >> a >> b >> c;
    a = a%10;
    if(a == 0 || a == 1 || a == 5 || a == 6){
     
        cout << a << endl;
    }else{
     
        if(a == 4 || a == 9){
     
            ll bc = pm(b,c,2);
            cout << abc[a][bc] << endl;
        }else {
     
            ll bc = pm(b,c,4);
            cout << abc[a][bc] << endl;
        }
    }
    system("pause");
    return 0;
}

C. String Invasion

https://atcoder.jp/contests/arc113/tasks/arc113_c

题意

给定字符串s,若 s i = s i + 1 ≠ s i + 2 s_i = s_{i+1} ≠ s_{i+2} si=si+1=si+2,则将 s i + 2 s_{i+2} si+2替换为 s i s_i si,求最多替换的次数。

思路

①从后往前遍历字符串,记录在两个相同且相邻的字符出现之前,各字符的出现次数。
②当出现两个相同且相邻的字符时,让结果加上这两个字符后面的字符串的长度,再减去这两个字符在后面的字符串中的出现次数(相同的字符不用修改)。
③因为后面的字符串已经被改动,所以要更新记录各字符的出现次数的数组。
④循环进行上述过程,直到字符串全都遍历完。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
string s;
int cnt[30];

int main(){
     
    IOS;
    cin >> s;
    ll res = 0;
    int len = s.length();
    for(int i = len-2;i >= 0;i--){
     
        if(s[i] == s[i+1]){
     
            int after = len -(i+2);
            res += after - cnt[s[i]-'a'];
            memset(cnt,0,sizeof(cnt));
            cnt[s[i]-'a'] = after;
        }
        cnt[s[i+1]-'a']++;
    }
    cout << res << endl;
    system("pause");
    return 0;
}

D.Sky Reflector

https://atcoder.jp/contests/arc113/tasks/arc113_d

题意

给定N,M,K, A i A_i Ai是第 i i i行的最小值, B j B_j Bj是第 j j j列的最大值,网格中每个数的大小不超过K,求(A,B)的所有可能性(答案对998244353取模)

思路

①对于n=1 和 m=1的情况特判。
②其他情况,假设A取 a 1 , a 2 , . . . a , n a_1,a_2,...a,_n a1,a2,...a,n,则设 a m a x a_{max} amax为这n个数中的最大值,对于B,若 b 1 , b 2 , . . . . , b m b_1,b_2,....,b_m b1,b2,....,bm ≥ a m a x ≥a_{max} amax则满足题意。
③通过行列的排列顺序不同,生成数组B,故对i进行枚举,可得公式
       ∑ i = 1 k ( i n − ( i − 1 ) n ) ∗ ( k − i + 1 ) m \sum_{i=1}^k(i^n-(i-1)^n)*(k-i+1)^m i=1k(in(i1)n)(ki+1)m
最后再对结果进行取余。
④需要用到快速幂。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mod = 998244353;
int n,m,k;

ll po(ll a,ll n){
     
    ll res = 1;
    while(n){
     
        if(n & 1){
     
            res = res * a % mod; 
        }
        a = a * a %mod;
        n >>= 1;
    }
    res %= mod;
    return res;
}

int main(){
     
    IOS;
    cin >> n >> m >> k;
    if(n == 1){
     
        cout << po(k,m) << endl;
    }else if(m == 1){
     
        cout << po(k,n) << endl;
    }else{
     
        ll res = 0;
        for(int i=1;i<=k;i++)
            res=(res+(ll)(po(i,n)-po(i-1,n)+mod)%mod*po(k-i+1,m)%mod)%mod;
        cout << res << endl;
    }
    system("pause");
    return 0;
}

你可能感兴趣的