新年伊始斩跌，終到百篇，龍年大吉。
題目1
題目鏈接
題目大意：
給出一個整數(shù)称勋，問該整數(shù)能否切分為兩個數(shù)字a和b，滿足：
1漓糙、a和b都不包括前導(dǎo)零铣缠，是一個正常的數(shù)字；
2昆禽、a和b都大于0蝗蛙；
3、b > a醉鳖；
如果可以捡硅，則輸出數(shù)字a和b；如果不可以則輸出-1盗棵；
輸入：
第一行壮韭，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例一行，單個整數(shù) (數(shù)字長度為2~8)
輸出：
每個樣例一行纹因，如果可以喷屋，則輸出數(shù)字a和b；如果不可以則輸出-1瞭恰；
Examples
input
5
20002001
391125
200200
2001000
12
output
2000 2001
39 1125
-1
200 1000
1 2
題目解析：
按照題目的要求屯曹，a要盡可能小，b要盡可能大惊畏。
由于題目給出的數(shù)字本身就合法恶耽，那么將第一個數(shù)字開始分為a，往后找到第一個非零的數(shù)字就分給b颜启，這樣b一定是最大的偷俭。
從字符串上切分好a和b，接下來就是轉(zhuǎn)成數(shù)字缰盏。
這里為了便于計(jì)算涌萤，從字符串a(chǎn)右邊開始往左邊枚舉每一個位置上的數(shù)字，就可以得到數(shù)字a口猜。（數(shù)字b同理形葬，也可以字符串切割后，用sscanf取巧）
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int k = 1, n = str.length();
while (k < n) {
if (str[k] != '0') break;
++k;
}
if (k >= n) {
cout << -1 << endl;
continue;;
}
int x = 0, y = 0;
int tmp = k - 1, val = 1;
while (tmp >= 0) {
x += val * (str[tmp] - '0');
--tmp;
val *= 10;
}
tmp = n - 1, val = 1;
while (tmp >= k) {
y += val * (str[tmp] - '0');
--tmp;
val *= 10;
}
if (x < y) cout << x << " " << y << endl;
else cout << -1 << endl;
}
}
}
ac;
題目2
題目鏈接
題目大意：
給出一個01字符組成的字符串??暮的，現(xiàn)在可以對字符串進(jìn)行任意次下面操作：
1笙以、刪除字符串中的某個一個字符，代價為1冻辩；
2猖腕、調(diào)換兩個位置上的字符拆祈，代價為0；
現(xiàn)在要求倘感，若干次操作后的字符串t放坏，t上面每一個字符都與原來字符串s的字符相反，比如說：
s=011
那么t=10老玛，最小操作代價是1淤年，移除一個字符1，然后交換一次0蜡豹、1的位置麸粮；
s=111100
那么t=00，最小操作代價是4镜廉，移除所有字符1弄诲；
問生成滿足要求的字符串t，最小的代價是多少娇唯。（注意移除所有字符也滿足要求）
輸入：
第一行齐遵，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例一行，字符串?? (1≤ |??| ≤2?1e5）
輸出：
每個樣例一行塔插，輸出滿足題目要求的最小代價梗摇；
Examples
input
4
0
011
0101110001
111100
output
1
1
0
4
題目解析：
按照題目的要求，直接看最終字符串t的樣式想许，比如說s=111100伶授，那么t=001111；
那么只需要累計(jì)原來0伸刃、1的數(shù)字?jǐn)?shù)量，然后從左到右枚舉t的位置逢倍，直到剩下的字符無法填充捧颅，那么就得到t的最大長度；
得到t的最大長度k较雕，那么需要移除的字符串長度就是n--k碉哑。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int n = str.length(), x = 0, y = 0;
for (int i = 0; i < n; ++i)
if (str[i] == '0') ++x;
else ++y;
int k = 0, cntX = x, cntY = y;
while (k < n) {
if (str[k] == '0') {
if (y > 0) --y;
else break;
}
else {
if (x > 0) --x;
else break;
}
++k;
}
if (x + y == 0) {
cout << 0 << endl;
}
else {
cout << n - k << endl;
}
}
}
}
ac;
題目3
題目鏈接
題目大意：
給出一個空的數(shù)組，現(xiàn)在有兩個操作：
操作1亮蒋，往數(shù)組添加一個數(shù)字2^x扣典；
操作2，詢問數(shù)組中的若干個數(shù)字慎玖，數(shù)字和是否可以為w贮尖；
輸入：
第一行，整數(shù)?? 表示m個操作 (1≤m≤100000)
每個操作一行
操作1趁怔，是輸入1和x (0≤x≤29 ).
操作2湿硝，是輸入2和w薪前；(0≤w≤1e9 ).
輸出：
每個操作2輸出一行，存在則輸出YES关斜，不存在輸出NO示括；
Examples
input
5
1 0
1 0
1 0
2 3
2 4
output
YES
NO
題目解析：
題目的數(shù)據(jù)范圍簡化了題目，首先x比較小痢畜，數(shù)組中最多只有30個整數(shù)類型垛膝，那么可以按照這個規(guī)則聚類；
其次丁稀，在判斷數(shù)組是否存在某個元素和時吼拥，可以從大到小遍歷數(shù)組，對于某個元素y如果小于等于當(dāng)前w二驰，則優(yōu)先取用扔罪，并且w=w-y，直到數(shù)組末尾桶雀；如果此時w=0矿酵，則有解，否則無解矗积；
class Solution {
static const int M = 536870912; // 2^29
int a[30];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int k, x;
cin >> k >> x;
if (k == 1) a[x]++;
else {
int cur = M;
for (int i = 29; i >= 0; --i) {
if (a[i] > 0 && x >= cur) {
int left = 1, right = a[i] + 1;
int find = left;
while (left < right) {
int mid = (left + right) / 2;
lld sum = 1LL * mid * cur;
if (sum > x) {
right = mid;
}
else {
find = mid;
left = mid + 1;
}
}
x -= find * cur;
}
cur /= 2;
}
cout << (x == 0 ? "YES" : "NO") << endl;
}
}
}
}
ac;
題目4
題目鏈接
題目大意：
有兩個整數(shù)n和k全肮，n表示字符串長度，k表示字符串由前k個小寫字符棘捣；
現(xiàn)在需要構(gòu)造一個字符串s辜腺，要求任何長度為n的字符串腺逛，都是字符串s的子序列色建；
輸入：
第一行茴她，整數(shù)?? 表示t個樣例 ?? (1≤??≤676)
每個樣例一行靴迫，整數(shù)n和k (1≤??≤26 ) and (1≤??≤26 ).
輸出：
每個樣例一行玉罐，輸出字符串s定拟，如果有多個則輸出最短長度的字符串鼻弧；
Examples
input
4
1 2
2 1
2 2
2 3
output
ab
aa
baab
abcbac
題目解析：
題目的要求习霹，所有常讀為n的字符串呜投，在拼接的時候就可以看成是n個選擇加匈，每次從k個字符中選擇一個；
那么在構(gòu)造的時候仑荐，可以采用這樣的策略：
我們重復(fù)abc/abc/abc這樣的字符串雕拼，每一組都相當(dāng)有k個不同字符的桶。
這樣構(gòu)造出來的結(jié)果就能滿足要求粘招。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) putchar('a' + j);
}
cout << endl;
}
}
}
ac;
題目5
題目鏈接
題目大意：
有一個正整數(shù)x啥寇，現(xiàn)在需要把x分成n個正整數(shù)，這些正整數(shù)之和是x；
現(xiàn)在要求示姿，n個正整數(shù)的最大公約數(shù)甜橱，盡可能的大；
輸入：
第一行栈戳，整數(shù)?? 表示t個樣例 ?? (1≤??≤1000)
每個樣例一行岂傲，整數(shù)??和 ?? (1≤??≤1e8) and (1≤??≤??).
輸出：
每個樣例一行，輸出最大的公約數(shù)子檀。
Examples
input
3
10 3
5 5
420 69
output
2
1
6
題目解析：
按照題目的要求镊掖，全部拆分成數(shù)字1，必然可以拆出滿足要求：
k-1個整數(shù)1褂痰，剩下的整數(shù)是x-n-1亩进，這些整數(shù)的最大公約數(shù)是1；
同理缩歪，假如最大公約數(shù)是2归薛，可以這么拆：
k-1個整數(shù)2，剩下的整數(shù)是x-2n-2匪蝙，最大的公約數(shù)是2主籍；
也就是說，假設(shè)最大公約數(shù)是k逛球，也可以這么安排：n-1個整數(shù)k千元，剩下是x-kn-k；
由于題目的范圍不大颤绕，那么枚舉最大公約數(shù)的數(shù)字就好幸海。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int x, n;
cin >> x >> n;
int k = sqrt(x) + 1;
int ans = 1;
for (int i = 1; i <= k; ++i) {
if (x % i == 0) {
if (i >= n) ans = max(ans, x / i);
if (x / i >= n) ans = max(ans, i);
}
}
cout << ans << endl;
}
}
}
ac;
