Codeforces Round #600 (Div. 2)
A. Single Push
-
思路:水题
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
const int N = 1e5 + 10;
int t, n;
int a[N], b[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t -- ){
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
for (int i = 1; i <= n; i ++ ){
cin >> b[i];
b[i] -= a[i];
}
vector<int> c;
bool flag1 = true;
int pos1 = 0, pos2 = 0;
for (int i = 1; i <= n; i ++ ){
if (b[i] < 0){
flag1 = false;
break;
}
}
if (!flag1){
cout << "NO
";
continue;
}
for (int i = 1; i <= n; i ++ ){
if (b[i] != 0){
pos1 = i;
break;
}
}
for (int i = n; i >= 1; i -- ){
if (b[i] != 0){
pos2 = i;
break;
}
}
for (int i = pos1; i <= pos2; i ++ )
c.push_back(b[i]);
bool flag2 = true;
for (int i = 0; i < c.size() - 1; i ++ ){
if (c[i] != c[i + 1]){
flag2 = false;
break;
}
}
if (!flag2){
cout << "NO
";
continue;
}
cout << "YES
";
}
return 0;
}
B. Silly Mistake
-
思路:模拟
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
const int N = 1e5 + 10;
int n, a, c1, c2, tot;
int b[N];
map<int, int> mp1, mp2;
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++ ){
cin >> a;
if (a > 0){
if (mp1[a] != 0)
c1 = 1;
else{
if (mp2[a] != 0)
c1 = 1;
mp1[a] ++ ;
mp2[a] ++ ;
c2 ++ ;
}
}
else{
if (mp1[-a] == 0)
c1 = 1;
else{
mp1[-a] -- ;
c2 -- ;
if (!c2){
b[ ++ tot ] = i;
mp2.clear();
}
}
}
}
if (c1 == 1 || c2 != 0){
cout << "-1
";
return 0;
}
cout << tot << "
";
for (int i = 1; i <= tot; i ++ )
cout << b[i] - b[i - 1] << " ";
return 0;
}
C. Sweets Eating
-
思路:贪心 排序后求前缀和搞搞
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
const int N = 2e5 + 10;
int n, m;
int a[N];
ll sum[N], ans[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++ ){
sum[i] = sum[i - 1] + 1ll * a[i];
if (i <= m)
ans[i] = sum[i];
else
ans[i] = ans[i - m] + sum[i];
}
for (int i = 1; i <= n; i ++ )
cout << ans[i] << " ";
return 0;
}
D. Harmonious Graph
-
思路:bfs遍历找到一个端点可以连到的最远点 找直接不能连通的点每次ans ++ 然后更新连通性即可
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
const int N = 2e5 + 10;
int n, m, maxx, tot, ans;
int vis[N], head[N];
struct Edge{
int v, nxt;
}e[N << 1];
void add(int u, int v){
e[ ++ tot ].v = v;
e[tot].nxt = head[u];
head[u] = tot;
}
void bfs(int x){
vis[x] = true;
maxx = max(maxx, x);
queue<int> q;
q.push(x);
while (!q.empty()){
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if (vis[v])
continue;
q.push(v);
vis[v] = true;
maxx = max(maxx, v);
}
}
}
int solve(int x){
int res = 0;
bfs(x);
for (int i = x + 1; i < maxx; i ++ ){
if (!vis[i]){
res ++ ;
bfs(i);
}
}
return res;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i ++ ){
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; i ++ )
if (!vis[i])
ans += solve(i);
cout << ans << "
";
return 0;
}