您的位置: 首页 > IT文章 > Codeforces 991 车牌号组合数学计算

Codeforces 991 车牌号组合数学计算

分类: IT文章 • 2024-03-06 22:09:53

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int gakki = 5 + 2 + 1 + 19880611 + 1e9;
const int MAXN = 3e5 + 5, MAXM = 6e6 + 5;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v, ll val)
{
        to[++tot] = v;
        value[tot] = val;
        nxt[tot] = Head[u];
        Head[u] = tot;
}*/
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int a, b, c, n;
        cin >> a >> b >> c >> n;
        if (max(c, max(a, b)) > n)
        {
                cout << -1 << endl;
                return 0;
        }
        if (c > min(a, b))
        {
                cout << -1 << endl;
                return 0;
        }
        if (n - a - b + c < 1)
        {
                cout << -1 << endl;
                return 0;
        }
        cout << n - a - b + c << endl;
        return 0;
}

View Code

*10后就不会有精度问题了

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int gakki = 5 + 2 + 1 + 19880611 + 1e9;
const int MAXN = 3e5 + 5, MAXM = 6e6 + 5;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v, ll val)
{
        to[++tot] = v;
        value[tot] = val;
        nxt[tot] = Head[u];
        Head[u] = tot;
}*/
int num[105];
priority_queue<int, vector<int>, greater<int> > que;
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
                cin >> num[i];
                num[i] = num[i] * 10;
                que.push(num[i]);
                sum += num[i];
        }
        int level = 45 * n;
        int ans = 0;
        while (sum < level)
        {
                sum += 50 - que.top();
                que.pop();
                ans++;
        }
        cout << ans << endl;
        return 0;
}

View Code

一眼二分

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int gakki = 5 + 2 + 1 + 19880611 + 1e9;
const int MAXN = 3e5 + 5, MAXM = 6e6 + 5;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v, ll val)
{
        to[++tot] = v;
        value[tot] = val;
        nxt[tot] = Head[u];
        Head[u] = tot;
}*/
int num[105];
priority_queue<int, vector<int>, greater<int> > que;
ll n;
ll check(ll x)
{
        ll sum = 0;
        ll now = n;
        while (now > 0)
        {
                ll duce = min(x, now);
                sum += duce;
                now -= duce;
                now -= now / 10;
        }
        return sum;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin >> n;
        ll aim = n / 2 + n % 2;
        ll l = 0, r = 2 * n;
        ll mid;
        while (l < r - 1)
        {
                mid = (l + r) / 2;
                if (check(mid) >= aim)
                {
                        r = mid;
                }
                else
                {
                        l = mid;
                }
        }
        cout << r << endl;
        return 0;
}

View Code

DP或者贪心模拟即可

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int gakki = 5 + 2 + 1 + 19880611 + 1e9;
const int MAXN = 3e5 + 5, MAXM = 6e6 + 5;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v, ll val)
{
        to[++tot] = v;
        value[tot] = val;
        nxt[tot] = Head[u];
        Head[u] = tot;
}*/
char f[3][105];
char s[3][105];
string ch[3];
int n;
int ans = 0;
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        for (int i = 1; i <= 2; i++)
        {
                cin >> ch[i];
                n = ch[i].size();
                for (int j = 0; j < n; j++)
                {
                        f[i][j + 1] = ch[i][j];
                }
        }
        for (int i = 1; i <= 2; i++)
        {
                for (int j = 1; j <= n; j++)
                {
                        s[i][j] = f[i][j];
                }
        }
        int sumnow;
        for (int i = 1; i <= n - 1; i++)
        {
                sumnow = 0;
                for (int j = 1; j <= 2; j++)
                {
                        for (int k = i; k <= i + 1; k++)
                        {
                                if (s[j][k] == '0')
                                {
                                        sumnow++;
                                }
                        }
                }
                if (sumnow >= 3)
                {
                        ans++;
                        for (int j = 1; j <= 2; j++)
                        {
                                for (int k = i; k <= i + 1; k++)
                                {
                                        if (s[j][k] == '0')
                                        {
                                                s[j][k] = 'X';
                                        }
                                }
                        }
                        if (sumnow == 4)
                        {
                                s[2][i + 1] = '0';
                        }
                }
        }
        cout << ans << endl;
        return 0;
}

View Code

题意:

给你一个最多18位的数你可以任意排列或者删除某个数但是出现过的数至少要有一个且不能有前导零

问你有几种方案

解:

统计下每个数的个数然后DFS一下算下答案即可

/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int gakki = 5 + 2 + 1 + 19880611 + 1e9;
const int MAXN = 5e2 + 5, MAXM = 6e6 + 5;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v, ll val)
{
        to[++tot] = v;
        value[tot] = val;
        nxt[tot] = Head[u];
        Head[u] = tot;
}*/
int num[MAXN];
int nownum[MAXN];
ll anser = 0;
ll facnum[MAXN];
void init()
{
        facnum[0] = 1;
        for (int i = 1; i <= 20; i++)
        {
                facnum[i] = i * facnum[i - 1];
        }
}
ll calans ()
{
        ll ansnow = 0;
        for (int i = 0; i <= 9; i++)
        {
                ansnow += nownum[i];
        }
        ansnow = facnum[ansnow];
        for (int i = 0; i <= 9; i++)
        {
                ansnow /= facnum[nownum[i]];
        }
        return ansnow;
}
void getans (int x)
{
        if (x > 9)
        {
                anser += calans();
                if (nownum[0] > 0)
                {
                        nownum[0]--;
                        anser -= calans();
                        nownum[0]++;
                }
                return ;
        }
        if (num[x])
        {
                for (nownum[x] = 1; nownum[x] <= num[x]; nownum[x]++)
                {
                        getans(x + 1);
                }

        }
        else
        {
                getans(x + 1);
        }
}
int main ()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        init();
        ll pop;
        cin >> pop;
        while (pop > 0)
        {
                num[pop % 10]++;
                pop /= 10;
        }
        getans(0);
        cout << anser << endl;
        return 0;
}

View Code

Codeforces 991 车牌号组合数学计算

相关推荐