当前位置：首页 > article >正文

补题篇--codeforces

article 2024/11/15 10:59:42

传送门：Problem - 1881C - Codeforces

题目大意：

思路：

首先解决这个问题要知道一个 ( x , y ) 顺时钟旋转 90 ， 180 ， 270可以得到 ( y , n - x + 1 ) ，

( n - x + 1 , n - y + 1 ) ，( n - y + 1 , x )

由于一个字符只能增大，所以可以找到旋转位置的最大字符，每个字符都要变成最大字符，因此求出答案

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n; cin >> n;
    vector<vector<char>> arr(n + 1, vector<char>(n + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++) cin >> arr[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int temp1 = max({ arr[i][j] , arr[j][n - i + 1] , arr[ n - j + 1 ][i] , arr[n - i + 1][n - j + 1] }) - 'a';
            int temp2 = arr[i][j] + arr[j][n - i + 1] + arr[n - j + 1][i] + arr[n - i + 1][n - j + 1] - 4 * 'a';
            ans += 4 * temp1 - temp2;
        }
    }
    cout << ans / 4 << endl;
}
signed main()
{
    int tt; cin >> tt;
    while (tt--)solve();
    return 0;
}

传送门：Problem - 1879C - Codeforces

题目大意：

思路：

如何计算最小操作次数：相同的区间段只能保留一个数字 00011101001111 -> 3 3 1 1 2 4

需要删除的数字个数 sum = ( len1 - 1 ) + ( len2 - 1 ) + ( len3 - 1 ) ......

如何计算最短操作序列的个数：C( len - 1 , len ) == len，一个区间段需要删除的数字序列是 len，

而这些数 ( sum )做全排列，sum的阶乘答案就是 len * sum!

0110110001 -> 1 2 1 2 3 1 ->第一个序列不用删除，第二个序列 11 可以删除 2 个(第二个或第三个1) ，第三个序列不用删除，第四个序列删除 3 个，第五个序列不用删除，删除的这些数还有做全排列

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
const int mod = 998244353;
int f[N];
void solve()
{
    string s; cin >> s;
    int n = s.size();
    s = " " + s;
    int ans = 1;
    int sum = 0;
    int len = 1;
    for( int i = 2; i <= n; i++)
    {
        if( s[i] != s[i-1] ) 
        {
            ans = ans * len % mod ; 
            sum += ( len - 1 ); 
            len = 1;
        }
        else len++;
    }
    ans = ans * len % mod;
    sum += ( len - 1 );
    cout << sum << " " << ans * f[sum] % mod << endl;
}
signed main()
{
    f[0] = 1;
    for( int i = 1; i <= 2e5 ; i++ ) f[i] = f[i-1] * i % mod;
    // 预处理阶乘
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

传送门：Problem - 1877C - Codeforces

题目大意：

思路：

结论题：

当 k == 1 时，易得 a[ n + 1] = 0

当 k == 2 时，min( n - 1 , m ) + m / n

当 k == 3 时，m - min( n - 1 , m ) - m / n

当 k > 3 时，0

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n , m , k;
    cin >> n >> m >> k;
    if( k > 3 )
    {
        cout << 0 << endl;
    }
    else if( k == 1 )
    {
        cout << 1 << endl;
        
    }
    else if( k == 2 )
    {
        cout << min( n - 1 , m ) + m / n << endl;
       
    }
    else 
    {
        cout << m - min( n - 1 , m ) - m / n << endl;

    }
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

补题篇：Problem - A - Codeforces

题目大意：

思路：

水母与海蜇进行的是相同的操作，同一个周期中，选手 a , b 的做法，都是一样的

所以可以缩短周期，进行模拟

新的周期 k = ( 100 + ( k & 1 ) )

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
int a[N] , b[N];
void solve()
{
    int n , m , k;
    cin >> n >> m >> k;
    k = min( k , 100 + (k & 1) );
    for( int i = 1; i <= n; i++) cin >> a[i];
    for( int i = 1; i <= m ;i++) cin >> b[i];
    for( int i = 1; i <= k; i++)
    {
        if( i & 1 )
        {
            int i1 = 1 , i2 = 1;
            for( int i = 1; i <= n; i++) if( a[i1] > a[i] ) i1 = i;
            for( int i = 1; i <= m; i++) if( b[i2] < b[i] ) i2 = i;
            if( b[i2] > a[i1] ) swap( a[i1] , b[i2] );
        }
        else
        {
            int i1 = 1 , i2 = 1;
            for( int i = 1; i <= n ;i++) if( a[i1] < a[i] ) i1 = i;
            for( int i = 1; i <= m; i++) if( b[i2] > b[i] ) i2 = i;
            if( a[i1] > b[i2] ) swap( a[i1] , b[i2] );
        }
    }
    int sum = 0;
    for( int i = 1; i <= n; i++) sum += a[i];
    cout << sum << endl;
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

传送门：Problem - D - Codeforces

题目大意：

思路：

x 的倍数位置上应该放大数， y 的倍数位置上应该放小数，如果说一个位置是 x 的倍数，y的倍数，这个位置是没有贡献的（不计算）

len_x = n / x - n / lcm( x , y )

len_y = n / y - n / lcm( x , y )

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd( int a ,int  b)
{
    return b ? gcd( b , a % b ) : a;
}
int lcm( int a ,int  b)
{
    return a * b / gcd( a , b );
}
int sum ( int l ,int r )
{
    return ( l + r ) * ( r - l + 1 ) / 2;
}
void solve()
{
    int n , x , y;
    cin >> n >> x >> y;
    int temp = lcm( x , y );
    int a = n / x  - n / temp;
    int b = n / y - n / temp;
    int ans = 0;
    cout << sum( n - a + 1 , n ) - sum( 1 , b ) << endl;
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

传送门：Problem - D - Codeforces

题目大意：

思路：

插入 n - 2 个字符，一定会有一个二位数，由此作为突破口

f[i][j] （ 1 <= i <= n , 0 <= j <= 1）

f[i][0] 表示为前 i 个字符，并没有二位数，插入 i - 2 个字符的最小结果

f[i][1] 表示为前 i 个字符，有二位数，插入 i - 2 个字符的最小结果

状态转移：

f[i][0] = min( f[i-1][0] * ( s[i] - '0' ) , f[i-1][0] * ( s[i] - '0' ) )

f[i][1] = min( f[i-1][1] * ( s[i] - '0' ) , f[i-1][1] + ( s[i] - '0' ) , f[i-2][0] * ( 10 * ( s[i-1] - '0' ) + s[i] - '0' ),

f[i-2][0] + ( 10 * ( s[i-1] - '0' ) + s[i] - '0' ) );

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 25;
int f[N][2];
void solve()
{
    int n; string s;
    cin >> n >> s;
    s = " " + s;
    int a = s[1] - '0'; 
    int b = s[2] - '0';
    f[1][0] = a;
    f[1][1] = 2e18; // 不可能存在的状态
    f[2][0] = min( a * b , a + b );
    f[2][1] = 10 * a + b;
    for( int i = 3 ; i <= n; i++)
    {
        int a = s[i] - '0';
        int b = s[i-1] - '0';
        f[i][0] = min( f[i-1][0] * a , f[i-1][0] + a );
        f[i][1] = min({ f[i-1][1] * a , f[i-1][1] + a , f[i-2][0] + ( 10 * b + a ) , f[i-2][0] * ( 10 * b + a ) } );
    }
    cout << f[n][1] << endl;
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

传送门：登录—专业IT笔试面试备考平台_牛客网

题目大意：

思路：

类似于 dp 问题，定义为 sum 为能够表示的 <= sum 的数都能够表达出来

当 sum >= a[i] - 1 才能转移，假设 sum == 7 , a[i] == 9 此时数字8无法表示，

sum == 7 , a[i] == 8 就可以转移

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int sum = 0;
    int n; cin >> n;
    vector<int> a( n + 1 );
    for( int i = 1; i <= n; i++) cin >> a[i];
    sort( a.begin() + 1 , a.end());
    for( int i = 1; i <= n; i++)
    {
        if( sum >= a[i] - 1 )sum += a[i];
    }
    if( sum >= n )puts("Cool!");
    else cout << sum + 1 << endl;
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

传送门：Problem - C - Codeforces

题目大意：

给定数组 a ，一共有 n 个元素，请构造数组 b ，使得 a[i] * b[i] > sum ( sum 为数组 b 的和 )，

如果不能构造输出-1，如果能输出数组 b

思路：

结论题：类似的这种题可以往 gcd , lcm 这类问题上套

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd( int a ,int b )
{
    return b ? gcd( b , a % b ) : a;
}
int lcm( int a , int b )
{
    return a * b / gcd( a , b );
}
void solve()
{
    int n; cin >> n;
    vector<int> a( n + 1 );
    int sum = 1;
    for( int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum = lcm( sum , a[i] );
    }
    vector<int> ans( n + 1 );
    int temp = 0;
    for( int i = 1; i <= n ;i++)
    {
        ans[i] = sum / a[i];
        temp += ans[i];
    }
    if( temp >= sum )
    {
        cout << -1 << endl;
        return;
    }
    else
    {
        for( int i = 1; i <= n; i++)cout << ans[i] << " ";
        cout << endl;
    }
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}

查看全文

http://www.kler.cn/a/308128.html