題目鏈接：https://codeforces.com/contest/1462
以后要堅持補題寫題解呀~
A:Favorite Sequence
題目大意
給一個序列，按照序列首尾首尾的取元素
思路
vector簡單模擬
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[305];
int main(){
int t; cin >> t;
while(t --){
int n; cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
vector<int> v;
int l = 1, r = n;
while(l < r){
v.push_back(a[l]);
v.push_back(a[r]);
l ++; r --;
}
if(n & 1) v.push_back(a[l]); //如果n為奇數，則會多出一個值
for(int i = 0; i < v.size(); i ++){
if(i) cout << " ";
cout << v[i];
}
cout << endl;
}
return 0;
}B:Last Year's Substring
題目大意
給一個字串，問能否最多洗掉連續一段使得剩下的字串是“2020”？
思路
因為最多洗掉一段，中間兩邊分別判斷一下就好了
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
char a[305];
int main(){
int t; scanf("%d",&t);
while(t --){
int n; scanf("%d%s",&n, a + 1);
if(a[1] == '2' && a[2] == '0' && a[3] == '2' && a[4] == '0') puts("YES"); //從5開始刪
else if(a[1] == '2' & a[2] == '0' && a[3] == '2' && a[n] == '0') puts("YES"); //從4開始刪
else if(a[1] == '2' && a[2] == '0' && a[n - 1] == '2' && a[n] == '0')puts("YES");//從3開始刪
else if(a[1] == '2' && a[n - 2] == '0' && a[n - 1] == '2' && a[n] == '0') puts("YES");//從2開始刪
else if(a[n - 3] == '2' && a[n - 2] == '0' && a[n - 1] == '2' && a[n] == '0') puts("YES");//從1開始刪
else puts("NO");
}
return 0;
}C:Unique Number
題目大意
輸出最小的數位和等于x并且各個數位都不一樣的值
思路
低位的數位越大越好，最后一位從9開始列舉，倒數第二位從8開始列舉，以此類推，，，減到n不夠減，當n>45是，出 -1
AC代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int main(){
int t; scanf("%d",&t);
while(t --){
int n; scanf("%d",&n);
if(n > 45) {
puts("-1");
continue;
}
int d = 9;
string a;
char ch;
while(n){
if(n <= d){
ch = n + '0';
a = ch + a;
n = 0;
} else{
n -= d;
ch = d + '0';
d --;
a = ch + a;
}
}
cout << a << endl;
}
return 0;
}
D:Add to Neighbour and Remove
題目大意
給出一個序列，相鄰的可以左右合并，問最后最多可以分成多少段相同的值，
思路
總和是sum，列舉分成的份數（當然就是sum的因子啦），然后更新最小值
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[3005], n;
ll cal(ll x){
ll ans = 0, res = 0;
int i = 1;
while(i <= n){
res += a[i ++];
if(res == x){
res = 0;
continue;
}
if(res > x) return n - 1; // 分不了的話只能合并成一個了
ans ++;
}
return ans;
}
int main(){
int t; scanf("%d",&t);
while(t --){
scanf("%d",&n);
ll sum = 0;
for(int i = 1; i <= n; i ++){
scanf("%d",&a[i]);
sum += a[i];
}
ll ans = n - 1;
for(ll i = 1; i * i <= sum; i ++){
if(sum % i == 0){ //可以分成i份和sum/i份
ll a1 = cal(i);
ll a2 = cal(sum / i);
ans = min(ans, min(a1, a2));
}
}
printf("%lld\n", ans);
}
return 0;
}E1:Close Tuples (easy version)
題目大意
給出一個序列，抽出3個數，這3個數的最大值減去最小值小于等于2，問能抽出多少組數
思路
這是簡單版本，那map存個數，分類討論，六種情況：【a,a,a】【a,a,a+1】【a,a+1,a+1】【a,a,a+2】【a,a+2,a+2】【a,a+1,a+2】
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
map<int, int> mp;
int main(){
int t; scanf("%d",&t);
while(t --){
int n; scanf("%d",&n);
mp.clear();
while(n --){
int x; scanf("%d",&x);
mp[x] ++;
}
ll ans = 0;
for(auto it : mp){
int d = it.first;
int num = it.second;
if(num >= 3) ans += 1ll * num * (num - 1) * (num - 2) / 6; //a,a,a
if(mp.count(d + 1)){
int dd = mp[d + 1];
if(num >= 2) ans += 1ll * num * (num - 1) / 2 * dd;//a,a,a+1
if(dd >= 2) ans += 1ll * dd * (dd - 1) / 2 * num;//a,a+1,a+1
if(mp.count(d + 2)) {
ans += 1ll * num * mp[d + 1] * mp[d + 2];//a,a+1,a+2
}
}
if(mp.count(d + 2)){
int ddd = mp[d + 2];
if(ddd >= 2) ans += 1ll * ddd * (ddd - 1) / 2 * num;//a,a+2,a+2
if(num >= 2) ans += 1ll * num * (num - 1) / 2 * ddd;//a,a,a+2
}
}
printf("%lld\n",ans);
}
return 0;
}E2:Close Tuples (hard version)
題目大意
和上題一樣但是m,k變成未知數，資料很大結果要取mod
思路
給的時限很多，可以雙指標列舉最左邊的數，然后剩下的數中取m-1個數，求個組合數
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
ll fac[maxn], inv[maxn];
ll _pow(ll a, ll b){
ll ans = 1;
while(b){
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void init(){ //預處理階乘數和階乘數的逆元
fac[0] = 1;
for(int i = 1; i < maxn; i ++)
fac[i] = fac[i - 1] * i % mod;
inv[maxn - 1] = _pow(fac[maxn - 1], mod - 2);
for(int i = maxn - 2; i >= 0; i --)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll c(ll a, ll b){ //求組合數
if(a < b) return 0;
return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
ll a[maxn];
int main(){
init();
int t; scanf("%d",&t);
while(t --){
int n, m, k;
scanf("%d%d%d",&n,&m,&k);
for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);
sort(a + 1, a + n + 1);
int l = 1;
ll ans = 0;
for(int r = m; r <= n; r ++){
while(a[r] - a[l] > k) l ++; //滿足區間內跨度小于等于k
if(r - l + 1 < m) continue; //滿足區間內數量大于等于m
ans = (ans + c(r - l, m - 1)) % mod;
}
printf("%lld\n", ans);
}
return 0;
}F:The Treasure of The Segments
題目大意
給你n個二元組，代表線段的左右端點，問最少刪幾條線段，使得剩下當中存在一個線段與所有剩下的所有線段都有交集，
思路
列舉每一個二元組作為那個特殊線段時需要刪的線段數，更新最小值，
AC代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int a[maxn], b[maxn];
int x[maxn], y[maxn];
int main(){
int t; scanf("%d",&t);
while(t --){
int n; scanf("%d",&n);
for(int i = 1; i <= n; i ++){
scanf("%d%d",&a[i], &b[i]);
x[i] = a[i];
y[i] = b[i];
}
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
int l, r, ans = n;
for(int i = 1; i <= n; i ++){
int l = (lower_bound(y + 1, y + n + 1, a[i]) - y) - 1; //右端點小于當前左端點的數量
int r = n - (upper_bound(x + 1, x + n + 1, b[i]) - x) + 1;//左端點大于當前右端點的數量
ans = min(ans, l + r);
}
printf("%d\n", ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/236667.html
標籤：其他