題目1

題目鏈接
題目大意：
有三個長度為n的字符串a(chǎn)奸笤、b勉耀、c，字符串都是小寫字符；
有一個長度為n的模版t惰帽，模版會與字符串a(chǎn)、b、c匹配，匹配規(guī)則如下：
1绣夺、假如模版的字符為小寫字母，則對應位置必須是相同字符才算匹配欢揖；
2陶耍、假如模版的字符為大寫字母，則對應位置則不能是相同字符才算匹配她混；
比如說模板abc和字符串a(chǎn)bc是匹配的烈钞，模板ABC和字符串def也是匹配的，模板ABC和字符串a(chǎn)bc是不匹配的坤按；

現(xiàn)在已知字符串a(chǎn)毯欣、b、c晋涣，問是否能夠構造一個模板t仪媒，要求字符串a(chǎn)和b是匹配的，字符串c是不匹配的谢鹊。

輸入：
第一行算吩，整數(shù)?? 表示t個樣例 ?? (1≤??≤1000)
每個樣例4行
第一行，整數(shù)??(1≤??≤20)佃扼，字符串長度
第2偎巢、3、4行兼耀，分別是字符串a(chǎn)压昼、b、c瘤运；

輸出：
每個樣例第一行窍霞，有解則輸出YES，無解則輸出NO拯坟；

Examples
input
4
1
a
b
c
2
aa
bb
aa
10
mathforces
luckforces
adhoccoder
3
acc
abd
abc

output
YES
NO
YES
NO

樣例解釋：
樣例1但金，直接用模板C
樣例3，可以用模板CODEforces

題目解析：
題目的意思比較繞郁季，但是匹配規(guī)則還是比較清晰的冷溃，可以先簡化題目。

先考慮字符串a(chǎn)和b梦裂，對于某個位置的字符：
如果a和b相同（假設都是字符x）似枕，那么模版可以字符x，也可以是字符X以外的大寫字符年柠；
如果a和b相同（假設是字符x和字符y）凿歼，那么模版必須是字符X、Y以外的大寫字符；

我們發(fā)現(xiàn)毅往，不管字符串a(chǎn)和b的取值牵咙，總是可以找到滿足要求的模版；

那么再考慮字符串c攀唯，要使得模版至少有一個配置是不匹配的洁桌，也就是至少有一個位置，字符串c該位置的字符與前面的都不同侯嘀。

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            string a, b, c;
            cin >> a >> b >> c;
            int ans = 0;
            for (int i = 0; i < n; ++i) if (a[i] != c[i] && b[i] != c[i]) ans = 1;
            cout << (ans > 0 ? "YES" : "NO") << endl;
        }
    }
}
ac;

題目2

題目鏈接
題目大意：
有n個棍子另凌，長度分別為2^????；
從這些棍子里面挑出3個戒幔，組成一個三角形吠谢；
想知道，一共有多少種選擇诗茎。
（三個棍子工坊，順序不同算一個組合，比如說1敢订、2王污、3 和 3、2楚午、1）

輸入：
第一行昭齐，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例2行
第一行 整數(shù)??，表示n個棍子(1≤??≤20)
第二行 n個整數(shù)矾柜，??1,??2,…,???? (0≤????≤?? ).

輸出：
每個樣例第一行阱驾，輸出能夠組合成三角形的數(shù)量。

Examples
input
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1

output
35
2
0
0

題目解析：
先分析題目的數(shù)據(jù)特點怪蔑。
由題目知道里覆，三個不同的數(shù)字是無法組合成三角；
那么缆瓣，有且僅有兩種可能：
1喧枷、三個數(shù)字相同；（這種情況就是組合數(shù)捆愁，C(x, 3) 從x個相同數(shù)組中選擇3個）
2、兩個數(shù)字相同窟却，剩下一個更小的數(shù)字昼丑；

將整數(shù)排序，從小到大夸赫。情況2的數(shù)量菩帝，就可以選定當前數(shù)字的2個棍子，再乘以前面的所有數(shù)字的數(shù)量。

typedef long long lld;
 
class Solution {
    static const int N = 301010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            map<int, int> h;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                h[a[i]]++;
            }
            lld ans = 0, sub = 0;
            for (map<int, int>::iterator it = h.begin(); it != h.end(); ++it) {
                int cnt = it->second;
                if (cnt >= 3) {
                    ans += 1LL * cnt * (cnt - 1) * (cnt - 2) / 6;
                }
                if (cnt >= 2) {
                    ans += 1LL * cnt * (cnt - 1) / 2 * sub;
                }
                sub += cnt;
            }
            cout << ans << endl;
        }
    }
}
ac;

題目3

題目鏈接
題目大意：
有一個整數(shù)數(shù)組a呼奢，數(shù)組每個元素的乘積是2023宜雀；
數(shù)組移除了k個整數(shù)，剩下長度為n的數(shù)組b握础；

現(xiàn)在已知數(shù)組長度n和數(shù)組b辐董，問能否找到原來的數(shù)組a。

輸入：
第一行禀综，整數(shù)?? 表示t個樣例 ?? (1≤??≤100)
每個樣例2行
第一行简烘，整數(shù)??和k (1≤??,??≤5)
第二行，n個整數(shù)??1,??2,…,????(1≤????≤2023)

輸出：
每個樣例第一行定枷，無解輸出NO孤澎，有解輸出YES；
如果有解欠窒，則第二行再輸出被移除的k個整數(shù)覆旭；

Examples
input
7
2 2
5 2
3 1
7 17 7
4 2
1 289 1 1
3 1
7 17 17
1 1
289
1 1
2023
1 3
1

output
1
1 0
0
0
1
3 0

題目解析：
題目的要求比較明確，當我們給出整數(shù)數(shù)組b時岖妄，假設最終的數(shù)組b乘積為m型将；
m能夠被2023整數(shù)時，剩余的k個數(shù)組就可以是[2023/m, 1衣吠， 1茶敏， 1】這樣的數(shù)組來組成。
如果m不能被整數(shù)缚俏，那么就無解了惊搏。

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            int ans = 2023, ok = 1;
            for (int i = 0; i < n; ++i) {
                int x;
                cin >> x;
                if (ans % x == 0) ans /= x;
                else ok = 0;
            }
            if (ok) {
                cout << "YES\n" << ans;
                while (k > 1) {
                    k--;
                    cout << " " << 1;
                }
                cout << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    }
}
ac;

題目4

題目鏈接
題目大意：
給出兩個整數(shù)a和b，現(xiàn)在要找到整數(shù)x忧换，滿足條件：
1恬惯、1≤??<??<??，且1≤??≤1e9亚茬；
2酪耳、a和b是x的因數(shù)，且是因數(shù)（x不算）中最大的兩個刹缝；

比如說12 的因數(shù)有 [1,2,3,4,6]碗暗，那么a和b就是4和6；

輸入：
第一行梢夯，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例一行言疗，整數(shù)?? , ?? (1≤??<??≤1e9)

輸出：
每個樣例一行，輸出滿足要求的x颂砸；（題目保證有解）

Examples
input
8
2 3
1 2
3 11
1 5
5 10
4 6
3 9
250000000 500000000

output
6
4
33
25
20
12
27
1000000000

題目解析：
先從小樣例開始分析噪奄，容易知道當a=1的時候死姚，答案是b^2；
當a=2的時候
[2, 3]=6
[2, 4]=8
[2, 5]=10
[2, 6]無解勤篮；（12的時候都毒，3、4因子更大）

當a=3的時候
[3, 4]=12
[3, 5]=15
[3, 6]無解碰缔；（12的時候账劲，因子4更大）

當a=4的時候
[4, 5]=20
[4, 6]=12
[4, 7]=28
[4, 8]=16
[4, 9]無解；（36的時候手负，因子3x12=36涤垫，12更大）

我們發(fā)現(xiàn)，有解/無解的時候竟终，與a蝠猬、b的因子有一個強關聯(lián)，

比如說[2, 6]無解统捶，實際上6=2x3榆芦，那不管乘以任何數(shù)字k，都容易產(chǎn)生2 * k喘鸟、3 * k這樣的因子匆绣，一定比2要大；
[4, 9]無解什黑，也是同理4=2x2, 9=3x3崎淳，理論上的有4、9因子的最小值就是2x2x3x3=36愕把，但是會產(chǎn)生很多較大因子拣凹。

比如說有解的時候，大多數(shù)值都是最小公倍數(shù)恨豁。
但是有例外是[2, 4]和[4, 8]嚣镜，當他們b整除a的時候，最小公倍數(shù)是b橘蜜，但是題目要求是x>b菊匿，所以x要乘以一個值k。
下面說明k的取值關系计福。

假設k=b/a跌捆，那么b=k * a, b * (b/a)=b * k=(a * k) * k
假如是b * 2的話，b * 2=a * k * 2象颖，那么因子里面就會多出來一個2 * a佩厚，此時如果一旦b/a != 2，那么必會有一個2 * a的因子 大于原來的因子a力麸；
假如是b * (b/a)的話可款，只會產(chǎn)生一個k * k的因子，a * k是等于b的克蚂，并且我們可以知道有解的條件是k * k<a

這樣題目的大體思路就有了闺鲸。
注意：最小公倍數(shù)的求法，可以用最大公約數(shù)來算埃叭。（我自己忘了摸恍，竟然嘗試用因數(shù)分解去做，結果超時了）

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    long gcd(lld a, lld b){
        if (b==0) return a;
        return gcd(b, a%b);
    }
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int a, b;
            cin >> a >> b;
            int n = a, m = b;
            if (m % n == 0) {
                // 表示b是a的倍數(shù)赤屋，此時只需要將m*(m / n)就行
                // 假設k=m/n立镶，那么m=k*n, m*(m/n)=m*k=(n*k)*k
                // 假如是m*2的話，m*2=n*k*2类早，那么因子里面就會多出來一個2*n媚媒，此時如果一旦m/n != 2，那么必然會有一個2*n的因子 大于原來的因子n涩僻；
                // 假如是m * (m/n)的話缭召，只會產(chǎn)生一個k*k的因子，n*k是等于m的逆日，并且我們可以知道有解的條件是k*k<n
                cout << m * (m / n) << endl;
            }
            else {
                lld ans = a * 1LL * b / gcd(a, b);
                cout << ans << endl;
            }
        }
}
ac;

題目5

題目鏈接
題目大意：
有n個整數(shù)的數(shù)組a嵌巷，現(xiàn)在有Alice和Bob兩個人玩游戲，Alice先手室抽。
游戲規(guī)則如下：
1搪哪、數(shù)組中只有一個元素時結束游戲，當前數(shù)字為最終結果坪圾；
2晓折、每次可以選擇數(shù)組2個整數(shù)，移除對應整數(shù)神年；然后將整數(shù)相加再除以2已维，向下取整，再乘以2已日，最終將數(shù)字重新加回去數(shù)組垛耳；（比如說[1,3]=4, [2,3]=4)

Alice的目標是讓結果盡可能大，Bob的目標是讓結果盡可能小飘千。
現(xiàn)在想知道堂鲜，當只有數(shù)組前k個數(shù)字參與游戲時（??=1,2,…,??），最終的游戲結果是什么护奈。

輸入：
第一行缔莲，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例2行
第一行，整數(shù)??(1≤??≤1e5)
第二行霉旗，n個整數(shù)??1,??2,…,???? (1≤????≤1e9)

輸出：
每個樣例一行痴奏，共n個整數(shù)蛀骇；第k個數(shù)字，表示只有前k個數(shù)字參與游戲時读拆，最終的結果擅憔。

Examples
input
4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1

output
31
6 8 16 18 22 26
3 12 24
7 20 30 48 50

題目解析：
先不考慮k的取值情況，只看整個數(shù)組都參與游戲檐晕。
數(shù)組中的數(shù)字暑诸，我們可以分為奇數(shù)和偶數(shù)，已知偶數(shù)+偶數(shù)辟灰、奇數(shù)+奇數(shù)的操作只會合并數(shù)字个榕，不會有任何變化。只有奇偶數(shù)相加芥喇，此時最終結果會-1西采。
這樣， 我們假設有x個奇數(shù)继控；
先手每次優(yōu)先消耗2個奇數(shù)苛让，產(chǎn)出1個偶數(shù)；
后手每次優(yōu)先消耗1個奇數(shù)+1個偶數(shù)湿诊，產(chǎn)出1個偶數(shù)狱杰；（偶數(shù)必然存在，因為先手會產(chǎn)出偶數(shù)）
這樣我們就可以得到一個策略：
n=1厅须，ans=sum（用sum來表示前n項和）
n=2仿畸，ans=sum
n=3=2+1，ans=sum-1
n=4=2+1 +1, ans=sum-2
n=5=2+1 +2, ans=sum-1
n=6=2+1 + 2+1, ans=sum-2
n=7=2+1 + 2+1 +1, ans=sum-3
...
依次類推朗和，我們知道3個奇數(shù)是一個循環(huán)错沽，最終ans= sum - (n + 2) / 3 + ((n + 1) % 3 == 0)

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            vector<lld> ans;
            lld sum = 0, cnt = 0;;
            for (int i = 0; i < n; ++i) {
                int k;
                cin >> k;
                sum += k;
                if (k % 2) ++cnt;
                if (i == 0) ans.push_back(sum);
                else {
                    ans.push_back(sum - (cnt + 2) / 3 + ((cnt + 1) % 3 == 0));
                }
            }
            for (int i = 0; i < n; ++i) {
                cout << ans[i] << " ";
            }
            cout << endl;
        }
    }
}
ac;