A (貪心）
思路：
字串的每一位將會從左到右依次被選擇，否則，被跳過的字符將會被對手選擇并向對手有利的方向修改，所以從左到右依次修改即可，
AC代碼如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;
#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);
int n, m, k;
int main()
{
int T;
cin >> T;
while (T --)
{
string s;
cin >> s;
for (int i = 0; s[i]; i ++)
{
if (i & 1)
{
if (s[i] < 'z') s[i] = 'z';
else s[i] = 'z' - 1;
}
else
{
if (s[i] > 'a') s[i] = 'a';
else s[i] = 'b';
}
}
cout << s << endl;
}
return 0;
}
B (列舉)
思路：
1：擊殺所有怪物所需血量小于英雄血量時，直接輸出 “YES”
2：否則，假如能成功，必定是與最后一個怪物同時死亡，所以只需列舉最后一個怪物并判斷英雄是否在死亡之時將怪物擊殺即可，
注意：由于范圍都是1e9，最好全開 long long，
AC代碼如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;
#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);
int n, m, k;
LL a[N], b[N], c[N];
int main()
{
int T;
cin >> T;
while (T --)
{
LL A, B;
cin >> A >> B >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 1; i <= n; i ++)
cin >> b[i];
for (int i = 1; i <= n; i ++)
{
c[i] = a[i] * ((b[i] + A - 1) / A);
B -= c[i];
}
bool flag = true;
if (B <= 0)
{
flag = false;
for (int i = 1; i <= n; i ++)
{
B += c[i];
if (B > 0)
{
LL kill = A * ((B + a[i] - 1) / a[i]);
if (kill >= b[i])
{
flag = true;
break;
}
}
B -= c[i];
}
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
C (二分）
思路：
首先判斷 a[1] 和 a[n] 是不是區域最小值，假如是則輸出，
否則：a[1] 到 a[2] 呈下降趨勢，a[n] 到 a[n - 1] 呈下降趨勢，則 2 ~ n-1中必定存在拐點，即區域最小值，
這時候發現一個性質:
當一個區間 [l, r]左右皆呈向中間下降的趨勢的時候，區間一定存在區域最小值，
不難想到在該區間中（不包含端點）任取一點 pos，該點要么是區域最小值，否則它一定存在一個相鄰點比它小，假設 a[pos - 1] < a[pos]，那么 [l, pos] 便可作為一個新的區間，便可縮小區間范圍，至于這個 pos 怎么取很明顯可以二分，
注意特判 n = 1 的情況
之前代碼有點問題，把區間端點寫錯了，代碼被新添的資料抬走了，現在代碼改正了，可以AC了
AC代碼如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;
#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);
int n, m, k;
int a[N];
int query(int pos)
{
cout << "? " << pos << endl;
int x;
cin >> x;
fflush(stdout);
return x;
}
void print(int pos)
{
cout << "! " << pos << endl;
fflush(stdout);
exit(0);
}
int main()
{
cin >> n;
if (n == 1) print(1);
a[1] = query(1);
a[2] = query(2);
a[n] = query(n);
a[n - 1] = query(n - 1);
bool flag = false;
if (a[1] < a[2])
{
print(1);
}
if (a[n] < a[n - 1])
{
print(n);
}
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
int left = query(mid - 1);
int right = query(mid + 1);
int now = query(mid);
if (left > now && right > now) print(mid);
else if (left < now) r = mid;
else l = mid;
}
print(l);
return 0;
}
D1 (貪心）
題意：
將序列從左到右依次加入到兩個集合中的一個，使得最后的結果最小，
思路：
遍歷序列，將數字依次存入佇列，再未遇到相鄰兩數相同的情況下先按兵不動，依據此后情況再做操作有利無害，
當第一次出現相鄰兩數相同時，此時兩集合為空，
此時 a[pos] == a[pos - 1] 并且 pos - 1 之前無相鄰兩數相同，
這時最優操作可為： 將 [1, pos - 1] 放入某一集合，將 pos 單獨放入另一集合，即將 pos 與 pos - 1 分開放置，使得貢獻為區間長度，如若不分開放置，則當前貢獻減一，使得之后貢獻最多加一，所以選擇前者，
設當前兩集合的末尾元素是 x，
當遍歷到 a[i], 此時佇列為空，但是 a[i] == x 時，只能將 a[i] 放入任意集合，貢獻為0，末尾元素依然為 x，
當再次遇到相鄰兩數相同時，思考此時能進行的操作：
設此時佇列對應的原區間為 [l, r] a[r] == a[r - 1]，
- a[r] == x.
1.假如佇列中存在相鄰兩數都不等于 x， 設 a[pos] != x && a[pos + 1] != x 那么可以將 [l, pos] 放在某一集合(a[l] 一定不等于 x)，將[pos + 1, r - 2] 放置在某一集合，再將[r - 1, r]分開放置到兩集合中,貢獻為區間長度，集合末尾依然為 x，
2.假若不存在相鄰兩數都不等于x，無論怎么放置，貢獻最高都為區間長度減一，并且集合末尾依然為 x，- a[r] != x.
此時將 [l, r - 1] 放置在某一集合，r 單獨放置于某一集合即可，貢獻為區間長度，集合末尾為 a[r]，在第一種情況中，需要記錄佇列中是否存在相鄰兩數都不等于 x，為了方便，不妨設集合剛開始為空時末尾元素都為 0，
重復操作，直到遍歷完序列為止，此時佇列剩余的元素也能算進貢獻，
想著挺麻煩，但是代碼挺短的
AC代碼如下:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;
#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double eps = 1e-9;
const double PI = acos(-1.0);
int n, m, k;
int a[N];
int q[N], hh = 0, tt = -1;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int b = 0, res = 0; //b為當前集合末尾元素
bool add = true;
for (int i = 1; i <= n; i ++)
{
if (hh > tt && a[i] == b) continue;
q[++ tt] = a[i];
if (hh < tt && q[tt] != b && q[tt - 1] != b) add = true;
if (hh < tt && q[tt] == q[tt - 1])
{
res += tt - hh + add;
b = q[tt];
tt = -1;
add = false;
}
}
res += tt - hh + 1;
cout << res << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258103.html
標籤：其他