A. Sweet Problem

There are three numbers. You can choose two - 1 at a time. How many times can you choose at most.

Idea: be greedy. The strategy is as follows:
1. First arrange the three numbers in order.
2. Then, if the largest and the second largest are different, reduce the largest and the smallest together and try to be as large as the second largest.
3. When a[2] is the same size as a[3], if a[1] has any left, share it equally with a[2] and a[3], and give whatever is more.
4. Finally, a[2] and a[3] are reduced together. The contribution takes the minimum value.

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll a[5];

int main()
{
    int kase;
    cin>>kase;
    while(kase--)
    {
        cin>>a[1]>>a[2]>>a[3];
        sort(a+1,a+1+3);
        ll ans = 0;;
        if(a[3] > a[2])
        {
            ll d = min(a[1], a[3] - a[2]);
            ans += d;
            a[3] -= d;
            a[1] -= d;
        }
        if(a[3]==a[2]&&a[1])
        {
            ll d = a[1] /2 ;
            ans += d*2;
            ans += a[1]%2;
            a[3] -= a[1]%2;
            a[3] -= d, a[2] -= d;
        }
        ans += min(a[2], a[3]);
        cout<<ans<<endl;
    }
    return 0;
}

B. PIN Codes

Give you n numbers and ask how many of them you can change at least to make them all different.

It is found that the maximum n is 10. So we only need to consider one bit. If the first three are the same, we'll change one. If the first three are different, there is no need to change.

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

map<string, int> Map;

int main()
{
    int kase;
    cin>>kase;
    while(kase--)
    {
        vector<string> s;
        Map.clear();
        int n; cin>>n;
        rep(i,1,n)
        {
            string tmp;
            cin>>tmp;
            s.pb(tmp);
            Map[tmp]++;
        }
        int cnt = 0;
        rep(i,1,n)
        {
            string cur = s[i-1];
            if(Map[cur]>1)
            {
                for(int j=0; j<=9; j++)
                {
                    s[i-1][3] = j + '0';
                    if(!Map[s[i-1]])
                    {
                        cnt++;
                        Map[s[i-1]] ++;
                        Map[cur] --;
                        break;
                    }
                }
            }
        }
        cout<<cnt<<'\n';
        rep(i,1,n) cout<<s[i-1]<<'\n';
    }
    return 0;
}

C. Everyone is a Winner!

Question meaning: ask you \ (\ lfloor n / 1 \ rfloor \), \ (\ lfloor n / 2 \ rfloor \), \ (\ lfloor n / 3 \ rfloor \)\ (\ lfloor n / N \ rfloor \), \ (\ lfloor n / (n + 1) \ rfloor \) how many different numbers are there.

In fact, this is an integer block template problem. If you traverse directly, it is the time complexity of O (n), and you must timeout.
We find that when n = 100, n/20 = 5, n/21 = n/22 = n/23 = n/24 = n/25 = 4, like [21,25], there is no need to traverse at all. When i=21, we can know where we can get the farthest when the quotient is 4 - to (n/(n/21)) = 25, so we can directly start from 25 in the next traversal. This is the idea of integer blocking. See code for details, time complexity O (\ (\ sqrt{n} \)).

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <unordered_map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

vector<ll> res;

void solve(ll n)
{
    for(ll l=1,r=0; l<=n; l = r+1)
    {
        res.pb(n/l);
        r = (n/ (n/l));
    }
}

int main()
{
    int kase;
    cin>>kase;
    while(kase--)
    {
        res.clear();
        ll n = read();
        solve(n); res.pb(0);
        sort(res.begin(),res.end());
        cout<<res.size()<<'\n';
        for(int i=0; i<res.size();i++)
        cout<<res[i]<<' ';
        cout<<'\n';
    }
    return 0;
}