Codeforces Round #690 (Div. 3)
A
给你一个序列是a1a3a5...a6a4a2;你要输出a1a2a3a4a5a6...
代码：
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cerr<<#x<<" : "<<x<<endl;
const int N=2e6+10;
const int mod=1e9+7;
typedef long long ll;
ll a[N],ans[N];
int main(){
int T;
cin>>T;
while(T--){
int n,k;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n&1){
int t=(n+1)/2;
for(int i=1;i<=t;i++){
ans[2*i-1]=a[i];
}
for(int i=n,j=1;i>t,j<t;i--,j++){
ans[j*2]=a[i];
}
}
else{
int t=(n)/2;
for(int i=1;i<=t;i++){
ans[2*i-1]=a[i];
}
for(int i=n,j=1;i>=t,j<=t;i--,j++){
ans[j*2]=a[i];
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
/*
*/
B
只可以删除一段连续的序列，问剩下的序列是否是“2020”；
思路： 判断四种情况
2020xxxxxx
202xxxxxx0
20xxxxxx20
2xxxxxx020
代码：
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cerr<<#x<<" : "<<x<<endl;
#define duipai freopen("in.txt", "r", stdin);freopen("test.txt", "w", stdout);
const int N=2e6+10;
const int M=1e4+5;
const int mod=998244353;
typedef long long ll;
ll qkpow(ll a, ll b) {
ll ans = 1%mod;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); } //��һ��������Ԫ
//ll a[N],ans[N];
//int a[N][N];
//char g[N][N];
int a[N];
void solve(){
int n;
cin>>n;
string s;
cin>>s;
if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[3]=='0') puts("YES");
else if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[n-1]=='0') puts("YES");
else if(s[0]=='2'&&s[1]=='0'&&s[n-2]=='2'&&s[n-1]=='0') puts("YES");
else if(s[0]=='2'&&s[n-3]=='0'&&s[n-2]=='2'&&s[n-1]=='0') puts("YES");
else if(s[n-4]=='2'&&s[n-3]=='0'&&s[n-2]=='2'&&s[n-1]=='0') puts("YES");
else puts("NO");
}
int main(){
int T;cin>>T;while(T--)
solve();
}
/*
100
3474 1962 4038
998244352 998244352 1000000000
998244352 998244352 1000000000
10000000 100000000 1000000000
*/
C
给你一个x输出，输出一个数各个数位都不同的，且各个数位相加等于x，多个答案输出最小，没有输出-1；（在int范围之内） 思路：
打表，有规律
代码：
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cerr<<#x<<" : "<<x<<endl;
const int N=2e6+10;
const int mod=1e9+7;
typedef long long ll;
//ll a[N],ans[N];
int a[]={
0,
1,
2,
3,
4,
5,
6,
7,
8,
9,
19,
29,
39,
49,
59,
69,
79,
89,
189,
289,
389,
489,
589,
689,
789,
1789,
2789,
3789,
4789,
5789,
6789,
16789,
26789,
36789,
46789,
56789,
156789,
256789,
356789,
456789,
1456789,
2456789,
3456789,
13456789,
23456789,
123456789,
-1,
-1,
-1,
-1,
-1
};
int main(){
int T;
cin>>T;
// for(int i=1;i<=50;i++){
// cout<<a[i]<<" ";
// }
//cout<<endl;
while(T--){
int n,k;
cin>>n;
cout<<a[n]<<endl;
}
}
/*
*/
D
给你一个序列，每次可以合并隔壁两个，最后全部数全部相等。问最少操作多少次。
最后一定可以全部相等，枚举分成多少部分
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cerr<<#x<<" : "<<x<<endl;
#define duipai freopen("in.txt", "r", stdin);freopen("test.txt", "w", stdout);
const int N=2e6+10;
const int M=1e4+5;
const int mod=998244353;
typedef long long ll;
ll qkpow(ll a, ll b) {ll ans = 1%mod;while (b) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
ll getInv(ll a) { return qkpow(a, mod - 2); } //��һ��������Ԫ
//ll a[N],ans[N];
//int a[N][N];
//char g[N][N];
int a[N];
void solve() {
int n;
cin >> n;
vector<ll> a(n);
ll sum = 0;
for (ll &x : a) {
cin >> x;
sum += x;
}
for (int i = n; i >= 1; i--) {
if (sum % i == 0) {
ll needSum = sum / i;//最后相同的数
ll curSum = 0;//判断是否可行
bool ok = true;
for (int j = 0; j < n; j++) {
curSum += a[j];
if (curSum > needSum) {//如果相加都不等于needsum，这种分法肯定不行。
ok = false;
break;
} else if (curSum == needSum) {
curSum = 0;
}
}
if (ok) {
cout << n - i << endl;
return;
}
}
}
}
int main(){
int T;cin>>T;while(T--)
solve();
}
/*
������
*/
E1
给你一个由1~n组成的a序列，元素可以重复，最多能找出几个这样的三元组满足： 1.i<j<z 2.max(ai,aj,az)−min(ai,aj,az)>=2
思路： 用一个桶记录每个数出现的次数，cnt[x]表示x的个数 假设三个连续的数，x,x+1,x+2
那么答案就有以下几种情况
- [x,x+1,x+2]
- [x,x+1,x+1]
- [x,x+2,x+2]
- [x,x,x+1]
- [x,x,x+2]
- [x,x,x]
答案：
-
cnt[x]⋅cnt[x+1]⋅cnt[x+2];
-
cnt[x]⋅cnt[x+1]⋅(cnt[x+1]−1)/2;
-
cnt[x]⋅cnt[x+2]⋅(cnt[x+2]−1)/2;
-
cnt[x]⋅(cnt[x]−1)/2⋅cnt[x+1];
-
cnt[x]⋅(cnt[x]−1)/2⋅cnt[x+2];
-
cnt[x]⋅(cnt[x]−1)⋅(cnt[x]−2)/6.
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define duipai freopen("in.txt", "r", stdin);freopen("test.txt", "w", stdout);
const int N=2e6+10;
const int M=1e4+5;
const int mod=998244353;
typedef long long ll;
ll qkpow(ll a, ll b) {ll ans = 1%mod;while (b) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
ll getInv(ll a) { return qkpow(a, mod - 2); } //求一个数的逆元
int n,m,x;
void solve() {
int n;
cin >> n;
vector<ll> cnt(n + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
ll ans = 0;
for (int i = 2; i < n; i++) {
ans += cnt[i - 1] * cnt[i] * cnt[i + 1];
}
for (int i = 1; i < n; i++) {
ans += cnt[i] * (cnt[i] - 1) / 2 * cnt[i + 1];
}
for (int i = 2; i <= n; i++) {
ans += cnt[i - 1] * cnt[i] * (cnt[i] - 1) / 2;
}
for (int i = 2; i < n; i++) {
ans += cnt[i - 1] * cnt[i + 1] * (cnt[i + 1] - 1) / 2;
}
for (int i = 2; i < n; i++) {
ans += cnt[i + 1] * cnt[i - 1] * (cnt[i - 1] - 1) / 2;
}
for (int i = 1; i <= n; i++) {
ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
}
cout << ans << "\n";
}
signed main(){
int T;cin>>T;while(T--)
solve();
}
/*
样例：
*/
拼多多集团-PDD公司福利 468人发布
