A.够级烧牌机

解析

本来写了快两千字的大模拟，最后怕大家看题累，修改到简易简易版了，就是简单判断一下对方发的牌是否是够级牌。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+10;
int b[30];
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int T=1;
    while (T--)
    {
        int n;
        cin>>n;
        string a;
        cin>>a;
        int w=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]=='X')w++;    //记录各种牌的数量
            if(a[i]=='J')b[11]++;
            if(a[i]=='Q')b[12]++;
            if(a[i]=='K')b[13]++;
            if(a[i]=='1'&&a[i+1]=='0'){b[10]++;continue;}
            if(a[i]>'0'&&a[i]<='9')
            {
                b[a[i]-'0']++;
            }
        }
        int s=0;
        for(int i=1;i<=13;i++)
        {
            if(b[i]!=0)
            {
                s++;//判断一下是否符合出牌规定
            }
        }
        if(s>=2){cout<<"NO"<<endl;continue;}//如果是两套牌或以上就可以直接判掉了
        else
        {
            if(w==0)
            {
                int sum=0,dx=0;
                for(int i=1;i<=13;i++)
                {
                    if(b[i])
                    {
                        dx=i;
                        sum=b[i];
                    }
                }
                if(dx>2&&dx<10){cout<<"NO"<<endl;continue;}
                if(dx==1&&sum>=2){cout<<"YES"<<endl;continue;}
                if(dx==2&&sum>=1){cout<<"YES"<<endl;continue;}
                if(dx==10&&sum>=5){cout<<"YES"<<endl;continue;}
                if(dx==11&&sum>=4){cout<<"YES"<<endl;continue;}
                if(dx==12&&sum>=3){cout<<"YES"<<endl;continue;}
                if(dx==13&&sum>=2){cout<<"YES"<<endl;continue;}
//这是无王的情况，就需要看够级牌的数量是否达标
            }
            else
            {
                cout<<"YES"<<endl;
            }
        }
    }
    return 0;
}

B.多重集合

解析

由题意显然可得此题是二分答案。 此题的难点在于check函数如何写，我们可以用multiset建立两个集合，一个用来存放1颜色的数字，一个用来存入0颜色的数字，由于此题单纯遍历两个集合会超时，我们可以考虑用lower_bound来二分集合里面的元素，由x+y=mid,我们可以推出y=mid-x，因此我们只需要查找另一个集合是否有大于等于mid-x的数，若有则删去该数，若没有则直接return false，循环结束说明mid满足，则return true，外边套用二分求右边界即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Fi first
#define Se second
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pii;
#pragma GCC optimize(2)


const int N=1e6+10;

Pii p[N];
int n;

bool check(int mid)
{
    multiset<int>st0,st1;
    for(int i=1;i<=n;i++){
        if(p[i].second==0){
            st0.insert(p[i].first);
            if(st1.empty()) continue;
            auto it=st1.lower_bound(mid-*st0.begin());
            if(it==st1.end()) return 0;
            st0.erase(st0.begin());
            st1.erase(it);
        }
        else{
            st1.insert(p[i].first);
            if(st0.empty()) continue;
            auto it=st0.lower_bound(mid-*st1.begin());
            if(it==st0.end()) return 0;
            st1.erase(st1.begin());
            st0.erase(it);
        }
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].first;
    for(int i=1;i<n;i++) cin>>p[i].second;
    int l=2,r=(int)2e8;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}

/*
   *
   *　　┏┓　　　┏┓+ +
   *　┏┛┻━━━┛┻┓ + +
   *　┃　　　　　　　┃
   *　┃　　　━　　　┃ ++ + + +
   *  ████━████+
   *  ◥██◤　◥██◤ +
   *　┃　　　┻　　　┃
   *　┃　　　　　　　┃ + +
   *　┗━┓　　　┏━┛
   *　　　┃　　　┃ + + + +Code is far away from 　
   *　　　┃　　　┃ + bug with the animal protecting
   *　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
   *　　　┃ 　　　　　　 ┣┓
   *　　  ┃ 　　　　　 　┏┛
   *　    ┗┓┓┏━┳┓┏┛ + + + +
   *　　　　┃┫┫　┃┫┫
   *　　　　┗┻┛　┗┻┛+ + + +
*/

C. 粽落谁手

解析

只奇偶的才能换，也就是说相同的奇偶性是不能交换的，换句话说也就是相同奇偶性的数他们的相对位置是不变的。那么我们只需要分别对于奇数和偶数观察他们是否是有序的即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Fi first
#define Se second
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pii;
#pragma GCC optimize(2)

const int N=1e6+10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n,x;
    cin>>n;
    int ji=0,ou=0;
    bool is=1;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x%2==1){
            if(x<ji) is=0;
            ji=x;
        }
        else{
            if(x<ou) is=0;
            ou=x;
        }
    }
    if(is) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
    return 0;
}

/*
   *
   *　　┏┓　　　┏┓+ +
   *　┏┛┻━━━┛┻┓ + +
   *　┃　　　　　　　┃
   *　┃　　　━　　　┃ ++ + + +
   *  ████━████+
   *  ◥██◤　◥██◤ +
   *　┃　　　┻　　　┃
   *　┃　　　　　　　┃ + +
   *　┗━┓　　　┏━┛
   *　　　┃　　　┃ + + + +Code is far away from 　
   *　　　┃　　　┃ + bug with the animal protecting
   *　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
   *　　　┃ 　　　　　　 ┣┓
   *　　  ┃ 　　　　　 　┏┛
   *　    ┗┓┓┏━┳┓┏┛ + + + +
   *　　　　┃┫┫　┃┫┫
   *　　　　┗┻┛　┗┻┛+ + + +
*/

D.zbw的端午节签到题——礼物篇

解析

简单dp题

注意不重复，例如00A中只有0,A,0A这三种（样例有点欺诈了但问题不大） 数据大小为1e6，所以不可能暴力，从十六进制下手进行dp即可，具体解法看下方代码

代码

int a[1000010];
int dp[20]={0};
int main(){
    string s;
    cin>>s;
//第一步先把字符串转化为数组（按照16进制形式转化）
    for(int i=0;i<s.size();i++)
{
        if(s[i]>='A'&&s[i]<='Z')
{
            a[i]=(s[i]-'A')+10;
        }
        else 
a[i]=s[i]-'0';
    }
//然后遍历数组，dp[i]表示以i结尾的优美串的数量
    for(int i=0;i<s.size();i++)
{
        dp[a[i]]=1;
        for(int j=0;j<t;j++)
{
            dp[a[i]]+=dp[j];
          }
    }
    ll sum=0;
//sum表示答案,十六进制所以就最多有16个数字结尾的dp[i],相加就行
    for(int i=0;i<16;i++)
{
        sum+=dp[i];
    }
    cout<<sum;
    return 0;
}

E.发粽子的 LU

解析

对于当前第 $i$ 名同学，如果粽子数量达不到 $m$ 只，则一定进行分配，因为前面粽子经过分配都达到 $m$ 只，考虑贪心，所以应选择 $[i, i + k - 1]$ 为分配区间，且第 i 名同学分够粽子后剩下粽子应分给该区间内的其他同学，具体思路见代码

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, num;
int a[5005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k >> num;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        // 当前需要这么多
        int now = m - a[i];
        // 要加这么多次
        int cnt = now / num + (now % num > 0);
        ans += cnt;
        int sum = cnt * num; // 一共这么多，可以分配给 k 个
        for (int j = i; j <= i + k - 1 && j <= n; j++)
        {
            if (sum > m - a[j])
            {
                sum -= (m - a[j]);
                a[j] = m;
            }
            else
            {
                a[j] += sum;
                sum = 0;
                break;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

F.欢乐端午节

解析

分两种情况：

1. p不是q的倍数，这种情况最大的x必然是p
2. p是q的倍数：

• 这时候，p和q共有的是q以及它的因子，要想合理的缩小p的范围来使$p$，只要用$q$的因子整除$p$，直到$p\%q \ !=0$就可以了，这样得到的x（p不断除以 q的因子 ），由于除的缘故，$x$必然是$p$的因子且不是$q$的倍数（模!=0），于是就可以：用p除以q的各个因子，得到x，与最大值比较并更新

再用$x/m$得到答案。

代码

#include <cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll t, p, q, ans,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
        cin >> p >> q >> m;
        if (p % q) {//如果p不是q的倍数（包括p<q），那么最大的x就是p
            cout << p / m<< endl;
        }
        else {
            ans = -1;//初始化
            ll low = p;
            while (low % q == 0) {//如果p是q的倍数的话，去除p中所有等于q的因子,直到p不是q的倍数
                low /= q;
            }
            ans = max(ans, low);
            for (ll i = 2;i * i <= q; i++) {//找q的因子，这样不用开方
                if (q % i == 0) {//如果是因子
                    ll low1 = p, low2 = p, lowq = q / i;
                    //因子成对，所以每个因子有两种情况
                    while (low1 % q == 0) {//当p包含q时，从p中慢慢去除q的因子,直到p不是q的倍数
                        low1 /= i;
                    }
                    ans = max(ans, low1);
                    while (low2 % q == 0) {//同理，这是第二种情况
                        low2 /= lowq;
                    }
                    ans = max(ans, low2);//要求最大的x
                }
            }
            cout << ans / m<< endl;
        }
    
    return 0;
}

G.小 LU 买粽子

1）知识点

这道题就是一道简单的01分数规划，再运用二分。

2）看题目

这道题要求单位价值（题目中的总美味值/总花费），我们假设单位美味值为x，我们就可以知道，x = Σv / Σc。

3）算法分析

1. 我们已经知道了这道题是要二分，那么我们就对单位价美味值进二分，也就是我们要求的答案。
2. 由上面我们设立的公式：变式可以得到 Σv - Σc * x = 0。我们在二分猜测答案的时候就以这个为基准（为什么呢？看下面）。
3. 如果我们选取的v和c使这个式子>0的话，说明至少还有一组v和c可以使得x更大：Σv - Σc * x > 0。这就是：x < Σv / Σc（算出了答案可以比二分猜测的x大）。
4. 所以我们就可以依照这个式子得到每个物品的权值，然后进行排序，选出最大的k个。进行****Σv - Σc * x > 0的判断。

4）算法操作

1. 这里要进行二分，首先按模板上二分： for (int i = 1; i <= 100; i++){ double mid = (l + r) / 2; if (judge(mid)) l = mid; else r = mid; } //这里用循环100次保证精度很高，不用<eps保证不会死循环
2. 然后就是二分判断怎么写了。
3. 按上面的说法，就是把Σb - Σa * x作为权值，从大到小排序，并进行k个统计判断就好了： bool judge(double x) { for (int i = 1; i <= n; i++) w[i] = v[i] - x * c[i]; sort(w + 1, w + 1 + n, greater<double>()); double sm = 0; for (int i = 1; i <= k; i++) sm += w[i]; return sm > 0; }

5）打代码

1. 所以我们先把c，v输入了。
2. 然后二分猜测答案。
3. 不断缩小范围，按照上面讲的二分判断进行判断。
4. 下面全代码~

#include <bits/stdc++.h>
using namespace std; 

const int N = 1e4 + 5; 

int c[N], v[N], a[N]; 

int n, k; 

int get (int x) {
	for (int i = 1; i <= n; i++) {
		a[i] = v[i] - c[i] * x; 
	}
	sort(a + 1, a + n + 1, greater<int>()); 
	int res = 0; 
	for (int i = 1; i <= k; i++) {
		res += a[i]; 
	}
	return res; 
}

int main () {
	
	// freopen("std.in", "mx", stdin); 
	// freopen("std.out", "w", stdout); 
	
	ios::sync_with_stdio(0); 
	cin.tie(0), cout.tie(0); 

	cin >> n >> k; 
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> v[i]; 
	}
	int l = 1, r = 1e4; 
	while (l <= r) {
		int mid = l + r >> 1; 
		if (get(mid) < 0) r = mid - 1; 
		else l = mid + 1; 
	}
	cout << r; 
	return 0; 
}