Codeforces 946 课程表背包DP 数位DFS构造

给你A,B 两个数 1.a=0 OR b=0 break 2.a>=2b a=a-2b 3.b>=2a b=b-2a

如果只是单纯模拟肯定会超时

只需要简化 a>=2b --> a%=2b b>=2a --> b%=2a就可以

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int  maxm = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll mod = 3e7;

int main()

{

        ll a, b;

        cin >> a >> b;

        int flag = ;

        while (!flag)

        {

                ll moda = 1LL *  * a;

                ll modb = 1LL *  * b;

                if (a ==  || b == )

                {

                        break;

                }

                if (a >= 1LL *  * b)

                {

                        a = a % modb;

                        continue;

                }

                else

                {

                        if (b >= 1LL *  * a)

                        {

                                b = b % moda;

                                continue;

                        }

                        else

                        {

                                break;

                        }

                }

                //cout << a << " " << b << endl;

        }

        cout << a << " " << b << endl;

}

子序列和子串要分清楚。。

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int  maxm = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll mod = 3e7;

int num[];

int zimu[];

int len;

int flag=;

void dfs(int x, int now)

{

        if(now==)

        {

                flag=;

                return;

        }

        for (int i = x; i <= len; i++)

        {

                if (num[i] <= now)

                {

                        num[i] = now;

                        dfs(i + , now + );

                        break;

                }

        }

}

int main()

{

        for (int i = ; i <= ; i++)

        {

                zimu[i] = i;

        }

        string a;

        cin >> a;

        flag = ;

        len = a.size();

        if (len <= )

        {

                cout << - << endl;

                return ;

        }

        for (int i = ; i < len; i++)

        {

                num[i + ] = a[i] - 'a';

        }

        dfs(, );

        if (flag)

        {

                for (int i = ; i <= len; i++)

                {

                        char ch = 'a';

                        ch += num[i];

                        cout << ch;

                }

        }

        else

        {

                cout << - << endl;

        }

}

贪心不可做正解是背包DP

其中dp[i][j]表示前 i 天删去 j 节课所需要的最少上课时间

dp方程是 dp[i][j+k]=min(dp[i][j+k],dp[i-1][j]+ke[k]) 其中ke[i]表示的是当天除去i节课所需要最少上课时间

ke[i]需要用前缀和来算

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

const int maxn = ;

int pre[maxn];

char f[maxn];

int ke[maxn];

int dp[maxn][maxn];

int main()

{

        int n, m, K;

        cin >> n >> m >> K;

        for (int i = ; i <= n; i++)

        {

                mem(dp[i], 0x3f3f3f3f);

                mem(ke, 0x3f3f3f3f);

                scanf("%s", f + );

                for (int j = ; j <= m; j++)

                {

                        pre[j] = pre[j - ] + (f[j] == '');

                }

                if (pre[m] <= K)

                {

                        ke[pre[m]] = ;

                }

                for (int j = ; j <= m; j++)

                {

                        for (int k = j; k <= m; k++)

                        {

                                int len = pre[m] - pre[k] + pre[j - ];

                                if (len <= K)

                                {

                                        ke[len] = min(ke[len], k - j + );

                                }

                        }

                }

                for (int j = ; j <= K; j++)

                {

                        for (int k = ; j + k <= K; k++)

                        {

                                dp[i][j + k] = min(dp[i][j + k], dp[i-][j] + ke[k]);

                        }

                }

        }

        cout << dp[n][K] << endl;

}

给你一个数字，求一个比当前数字小的最大的漂亮数字

(漂亮数：所以在当前数中出现的数出现的次数为偶数次)

当长度为奇数时答案明显是len-1个9

偶数时就需要搜索找出最后面的字典序可以比原序列小的地方

如果空格数大于当前出现次数为奇数的数的个数就输出9

因为整体是偶数个数 0-9都是构造的成双出现的所以一定满足

如果找不到就输出len-2个9; (小的数例如10不用特殊处理因为题目保证答案一定存在)

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

const int maxn = 2e5 + ;

int cnt[maxn][];

char f[maxn];

int n;

int len;

void getans()

{

        int i, j, k;

        for (i = len; i >= ; i--)

        {

                for (j = (int)(f[i] - '') - ; j >= (i == ); j--)

                {

                        int now = ;

                        for (k = ; k <= ; k++)

                        {

                                now += cnt[i - ][k] ^ (k == j);

                        }

                        if (now <= len - i)

                        {

                                for (k = ; k < i; k++)

                                {

                                        cout << f[k];

                                }

                                cout << j;

                                for (k = ; k <= len - i - now; k++)

                                {

                                        cout << ;

                                }

                                for ( k = ; k >= ; k--)

                                {

                                        if (cnt[i - ][k] ^ (k == j))

                                        {

                                                cout << k;

                                        }

                                }

                                cout << endl;

                                return ;

                        }

                }

        }

        for (i = ; i <= len -  + (len % ); i++)

        {

                cout << ;

        }

        cout << endl;

}

int main()

{

        cin >> n;

        while (n--)

        {

                scanf("%s", f + );

                len = strlen(f + );

                for (int i = ; i <= ; i++)

                {

                        cnt[][i] = ;

                }

                for (int i = ; i <= len; i++)

                {

                        int now = f[i] - '';

                        for (int j = ; j <= ; j++)

                        {

                                cnt[i][j] = cnt[i - ][j] ^ (j == now);

                        }

                }

                getans();

        }

}

巴特西

Codeforces 946 课程表背包DP 数位DFS构造

最新文章

热门文章