Codeforces Round #618 (Div. 2)
原题
A题：
题意就是一串数，相加和乘积不能是0
思路：输入的时候判断0的个数，并和加1，然后输入完之后sum==0就在加一
// I want to AC
#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#include<assert.h>
#define ll long long
#define MODD 1000000007
#define pii pair<int,int>
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
//#define ll long long
using namespace std;
const int maxn = 1e9+7;
#define FOR(i, x, y) for (ll i = (x), _##i = (y); i < _##i; ++i)
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
ll inv(ll a, ll M) {
static ll x, y;
assert(exgcd(a, M, x, y) == 1);
return (x % M + M) % M;
}
//void gcd(ll a,ll b,ll &d,ll &x,ll &y){
// if(!b){
// d=a;x=1;y=0;
// }else{
// gcd(b,a%b,d,y,x);
// y-=x*(a/b);
// }
//}
//ll inv(ll a,ll n){
// ll d,x,y;
// gcd(a,n,d,x,y);
// return d==1?(x+n)%n:-1;
//}
// LL get_inv(LL a, LL M) {
// static LL x, y;
// assert(exgcd(a, M, x, y) == 1);
// return (x % M + M) % M;
// }
//欧拉函数
ll euler(ll n)
{
ll rt = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
{
rt -= rt / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
rt -= rt / n;
return rt;
}
bool st[1000005];
int primes[50005];
void prime(int n)
{
int cnt =0 ;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
}
for(int j=0;j<cnt&&i*primes[j]<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
break;
}
}
}
}
vector<int > div(int x){
vector<int > res;
for(int i=1 ;i<=x/i;i++) {
if(x%i==0){
res.push_back(i);
if(i!=x/i) res.push_back(x/i);
}
}
sort(res.begin(), res.end());
return res;
}
ll MOD = 1e9+7;
inline void read(int &x){
x=0;int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}
int lowbit(int x)
{
return x&(-x);
}
//ll bin(ll x, ll n, ll MOD) {
// ll ret = MOD != 1;
// for (x %= MOD; n; n >>= 1, x = mul(x, x, MOD))
// if (n & 1) ret = mul(ret, x, MOD);
// return ret;
// }
//ll C(ll n, ll m) { // m >= n >= 0
// if (m - n < n) n = m - n;
// if (n < 0) return 0;
// ll ret = 1;
// FOR (i, 1, n + 1)
// ret = ret * (m - n + i) % MOD * bin(i, MOD - 2, MOD) % MOD;
// return ret;
// }
// ll Lucas(ll n, ll m) { // m >= n >= 0
// return m ? C(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD : 1;
// }
//double dp[maxn],num[maxn];
//char ch [2500][2500];
int main() {
int n;cin >>n;
while(n--) {
int t; cin >>t;
int z =0 ,f =0 ;
int sum =0 ;int cnt =0 ;
int zz =0;
for(int i=0;i<t;i++){
int kk;cin >>kk;
if(kk==0){
kk++;
zz ++;
}
sum+=kk;
}
// cout<<zz<<" "<<ff<<endl;
if(sum==0 ){
zz++;
}
cout<<zz<<endl;
}
return 0;
}B题
题意：就是把给你的一个数组，分为两个，使其中间值相差最小（中间值就是位于数组的中间）
思路：直接把数组sort，一开始怕超时，但是想了想n*log(n)不能超时，然后就果断用了，直接输出中间两项就行了
// I want to AC
#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#include<assert.h>
#define ll long long
#define MODD 1000000007
#define pii pair<int,int>
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
//#define ll long long
using namespace std;
const int maxn = 1e9+7;
#define FOR(i, x, y) for (ll i = (x), _##i = (y); i < _##i; ++i)
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
ll inv(ll a, ll M) {
static ll x, y;
assert(exgcd(a, M, x, y) == 1);
return (x % M + M) % M;
}
//void gcd(ll a,ll b,ll &d,ll &x,ll &y){
// if(!b){
// d=a;x=1;y=0;
// }else{
// gcd(b,a%b,d,y,x);
// y-=x*(a/b);
// }
//}
//ll inv(ll a,ll n){
// ll d,x,y;
// gcd(a,n,d,x,y);
// return d==1?(x+n)%n:-1;
//}
// LL get_inv(LL a, LL M) {
// static LL x, y;
// assert(exgcd(a, M, x, y) == 1);
// return (x % M + M) % M;
// }
//欧拉函数
ll euler(ll n)
{
ll rt = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
{
rt -= rt / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
rt -= rt / n;
return rt;
}
bool st[1000005];
int primes[50005];
void prime(int n)
{
int cnt =0 ;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
}
for(int j=0;j<cnt&&i*primes[j]<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
break;
}
}
}
}
vector<int > div(int x){
vector<int > res;
for(int i=1 ;i<=x/i;i++) {
if(x%i==0){
res.push_back(i);
if(i!=x/i) res.push_back(x/i);
}
}
sort(res.begin(), res.end());
return res;
}
ll MOD = 1e9+7;
inline void read(int &x){
x=0;int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}
int lowbit(int x)
{
return x&(-x);
}
//ll bin(ll x, ll n, ll MOD) {
// ll ret = MOD != 1;
// for (x %= MOD; n; n >>= 1, x = mul(x, x, MOD))
// if (n & 1) ret = mul(ret, x, MOD);
// return ret;
// }
//ll C(ll n, ll m) { // m >= n >= 0
// if (m - n < n) n = m - n;
// if (n < 0) return 0;
// ll ret = 1;
// FOR (i, 1, n + 1)
// ret = ret * (m - n + i) % MOD * bin(i, MOD - 2, MOD) % MOD;
// return ret;
// }
// ll Lucas(ll n, ll m) { // m >= n >= 0
// return m ? C(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD : 1;
// }
//double dp[maxn],num[maxn];
//char ch [2500][2500];
int main() {
int n;cin >>n;
while(n--){
int t;cin >>t;
vector<ll > v;
for(int i=0;i<2*t;i++){
ll kk ; cin >>kk;
v.push_back(kk);
}
sort(v.begin(),v.end());
ll one =0 , two =0 ;
ll sum =0x7f7f7f ;
sum = v[(2*t-1)/2+1] - v[(2*t-1)/2];
cout<<sum<<endl;
}
return 0;
}C题
题意就是通过他给的函数（x|y-y）排出顺序来找出最大的数
思路：因为通过找规律，发现只有最大位置上的1唯一且存在，排在第一剩下随便拍就能得出答案（为啥，是这个，且后面不用管，找一下别的题解的图，本弱鸡不会上传图QAQ）
// I want to AC
#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#include<assert.h>
#define ll long long
#define MODD 1000000007
#define pii pair<int,int>
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
//#define ll long long
using namespace std;
const int maxn = 1e9+7;
#define FOR(i, x, y) for (ll i = (x), _##i = (y); i < _##i; ++i)
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
ll inv(ll a, ll M) {
static ll x, y;
assert(exgcd(a, M, x, y) == 1);
return (x % M + M) % M;
}
//void gcd(ll a,ll b,ll &d,ll &x,ll &y){
// if(!b){
// d=a;x=1;y=0;
// }else{
// gcd(b,a%b,d,y,x);
// y-=x*(a/b);
// }
//}
//ll inv(ll a,ll n){
// ll d,x,y;
// gcd(a,n,d,x,y);
// return d==1?(x+n)%n:-1;
//}
// LL get_inv(LL a, LL M) {
// static LL x, y;
// assert(exgcd(a, M, x, y) == 1);
// return (x % M + M) % M;
// }
//欧拉函数
ll euler(ll n) {
ll rt = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
rt -= rt / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
rt -= rt / n;
return rt;
}
bool st[1000005];
int primes[50005];
void prime(int n) {
int cnt =0 ;
for(int i=2; i<=n; i++) {
if(!st[i]) {
primes[cnt++]=i;
}
for(int j=0; j<cnt&&i*primes[j]<=n; j++) {
st[primes[j]*i]=true;
if(i%primes[j]==0) {
break;
}
}
}
}
vector<int > div(int x) {
vector<int > res;
for(int i=1 ; i<=x/i; i++) {
if(x%i==0) {
res.push_back(i);
if(i!=x/i) res.push_back(x/i);
}
}
sort(res.begin(), res.end());
return res;
}
ll MOD = 1e9+7;
inline void read(int &x) {
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}
int lowbit(int x) {
return x&(-x);
}
//ll bin(ll x, ll n, ll MOD) {
// ll ret = MOD != 1;
// for (x %= MOD; n; n >>= 1, x = mul(x, x, MOD))
// if (n & 1) ret = mul(ret, x, MOD);
// return ret;
// }
//ll C(ll n, ll m) { // m >= n >= 0
// if (m - n < n) n = m - n;
// if (n < 0) return 0;
// ll ret = 1;
// FOR (i, 1, n + 1)
// ret = ret * (m - n + i) % MOD * bin(i, MOD - 2, MOD) % MOD;
// return ret;
// }
// ll Lucas(ll n, ll m) { // m >= n >= 0
// return m ? C(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD : 1;
// }
//double dp[maxn],num[maxn];
//char ch [2500][2500];
ll dp[100000]= {0};
int main() {
int n;
cin >>n;
int pos=0;
for(int i=1; i<=n; i++)cin >>dp[i];
for(int i = 40; i>=0; i--) {
int num =0 ;
for(int j=1; j<=n; j++) {
if(((dp[j]>>i) &1)==0)num++;
else {
// cout<<j<<endl;
pos = j;
}
}
// cout<<num<<endl;
if(num==n-1)break;//only
}
//cout<<pos<<endl;
if(pos==0) {
for(int i=1; i<=n; i++) {
if(i!=1)cout<<" ";
cout<<dp[i];
}
cout<<endl;
} else {
cout<<dp[pos];
for(int i=1; i<=n; i++) {
if(i==pos) continue ;
cout<<" "<<dp[i];
}
cout<<endl;
}
return 0;
}D题（赛后补的）
题意很唬人，其实就是让你判断一下这个图形是否可以成为中心对称图形（（0,0）版本的）
思路：直接通过中心对称图形的性质来判断即可（这道题是赛后补的，初中的知识，都忘了。。。记录一下中心对称图形的对称中心是所有点相加和/所有个点，通过2*对称中心点-任意坐标点判断）
// I want to AC
#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#include<assert.h>
#define ll long long
#define MODD 1000000007
#define pii pair<int,int>
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
//#define ll long long
using namespace std;
const int maxn = 1e9+7;
#define FOR(i, x, y) for (ll i = (x), _##i = (y); i < _##i; ++i)
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
ll inv(ll a, ll M) {
static ll x, y;
assert(exgcd(a, M, x, y) == 1);
return (x % M + M) % M;
}
//void gcd(ll a,ll b,ll &d,ll &x,ll &y){
// if(!b){
// d=a;x=1;y=0;
// }else{
// gcd(b,a%b,d,y,x);
// y-=x*(a/b);
// }
//}
//ll inv(ll a,ll n){
// ll d,x,y;
// gcd(a,n,d,x,y);
// return d==1?(x+n)%n:-1;
//}
// LL get_inv(LL a, LL M) {
// static LL x, y;
// assert(exgcd(a, M, x, y) == 1);
// return (x % M + M) % M;
// }
//欧拉函数
ll euler(ll n) {
ll rt = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
rt -= rt / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
rt -= rt / n;
return rt;
}
bool st[1000005];
int primes[50005];
void prime(int n) {
int cnt =0 ;
for(int i=2; i<=n; i++) {
if(!st[i]) {
primes[cnt++]=i;
}
for(int j=0; j<cnt&&i*primes[j]<=n; j++) {
st[primes[j]*i]=true;
if(i%primes[j]==0) {
break;
}
}
}
}
vector<int > div(int x) {
vector<int > res;
for(int i=1 ; i<=x/i; i++) {
if(x%i==0) {
res.push_back(i);
if(i!=x/i) res.push_back(x/i);
}
}
sort(res.begin(), res.end());
return res;
}
ll MOD = 1e9+7;
inline void read(int &x) {
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}
int lowbit(int x) {
return x&(-x);
}
//ll bin(ll x, ll n, ll MOD) {
// ll ret = MOD != 1;
// for (x %= MOD; n; n >>= 1, x = mul(x, x, MOD))
// if (n & 1) ret = mul(ret, x, MOD);
// return ret;
// }
//ll C(ll n, ll m) { // m >= n >= 0
// if (m - n < n) n = m - n;
// if (n < 0) return 0;
// ll ret = 1;
// FOR (i, 1, n + 1)
// ret = ret * (m - n + i) % MOD * bin(i, MOD - 2, MOD) % MOD;
// return ret;
// }
// ll Lucas(ll n, ll m) { // m >= n >= 0
// return m ? C(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD : 1;
// }
//double dp[maxn],num[maxn];
//char ch [2500][2500];
ll x[100010], y [100010];
int main() {
int n;cin >>n;
ll midx=0 ; ll midy =0 ;
map<pair<ll ,ll> ,int >mp;
for(int i=0;i<n;i++){
cin >>x[i]>>y[i];
x[i]*=n;y[i]*= n;
midx+=x[i];midy+=y[i];
mp[make_pair(x[i],y[i])] =1 ;
}
midx/=n;midy/=n;
for(int i=0;i<n;i++){
if(mp[make_pair(2*midx-x[i],2*midy-y[i])]==0)return cout<<"NO"<<endl,0;
}
cout<<"YES"<<endl;
return 0;
}E题（赛后补的）
题意：就是让你通过题面上说的意思来使这个数组字典序最小
思路：看的大佬的思路，就是从后往前判断，只要当前的数num<之前的一个集合cnt,就把这个num加到这个集合里面，之后的双重for查找（大佬他们写的就不超时，我写的就超时，明明一样的思路qaq）
// I want to AC
#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#include<assert.h>
#define ll long long
#define MODD 1000000007
#define pii pair<int,int>
#include<stdio.h>
#include<string.h>
#include<bits/stdc++.h>
//#define ll long long
using namespace std;
const int maxn = 1e6+7;
#define FOR(i, x, y) for (ll i = (x), _##i = (y); i < _##i; ++i)
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
ll inv(ll a, ll M) {
static ll x, y;
assert(exgcd(a, M, x, y) == 1);
return (x % M + M) % M;
}
//void gcd(ll a,ll b,ll &d,ll &x,ll &y){
// if(!b){
// d=a;x=1;y=0;
// }else{
// gcd(b,a%b,d,y,x);
// y-=x*(a/b);
// }
//}
//ll inv(ll a,ll n){
// ll d,x,y;
// gcd(a,n,d,x,y);
// return d==1?(x+n)%n:-1;
//}
// LL get_inv(LL a, LL M) {
// static LL x, y;
// assert(exgcd(a, M, x, y) == 1);
// return (x % M + M) % M;
// }
//欧拉函数
ll euler(ll n) {
ll rt = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
rt -= rt / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
rt -= rt / n;
return rt;
}
bool st[1000005];
int primes[50005];
void prime(int n) {
int cnt =0 ;
for(int i=2; i<=n; i++) {
if(!st[i]) {
primes[cnt++]=i;
}
for(int j=0; j<cnt&&i*primes[j]<=n; j++) {
st[primes[j]*i]=true;
if(i%primes[j]==0) {
break;
}
}
}
}
vector<int > div(int x) {
vector<int > res;
for(int i=1 ; i<=x/i; i++) {
if(x%i==0) {
res.push_back(i);
if(i!=x/i) res.push_back(x/i);
}
}
sort(res.begin(), res.end());
return res;
}
ll MOD = 1e9+7;
inline void read(int &x) {
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}
int lowbit(int x) {
return x&(-x);
}
//ll bin(ll x, ll n, ll MOD) {
// ll ret = MOD != 1;
// for (x %= MOD; n; n >>= 1, x = mul(x, x, MOD))
// if (n & 1) ret = mul(ret, x, MOD);
// return ret;
// }
//ll C(ll n, ll m) { // m >= n >= 0
// if (m - n < n) n = m - n;
// if (n < 0) return 0;
// ll ret = 1;
// FOR (i, 1, n + 1)
// ret = ret * (m - n + i) % MOD * bin(i, MOD - 2, MOD) % MOD;
// return ret;
// }
// ll Lucas(ll n, ll m) { // m >= n >= 0
// return m ? C(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD : 1;
// }
//double dp[maxn],num[maxn];
//char ch [2500][2500];
const int N=1e6+1;
long long n,a[N],s,c,p[N],q[N],t;
int main() {
ios::sync_with_stdio(false);
cin >>n;
for(int i=1;i<=n;i++){
cin >>a[i];
// a[i] = a[i-1] + xx;
}
for(int i=1;i<=n;i++)
{
s=a[i],c=1;
while(t&&p[t]*c>=s*q[t])
s+=p[t],c+=q[t--];
p[++t]=s,q[t]=c;
}
for(int i=1;i<=t;i++){
for(int j=1;j<=q[i];j++)
printf("%.10f\n",(double)p[i]/q[i]);
// cout<<endl;
}
return 0;
}
投递中移(苏州)软件技术有限公司等公司10个岗位 >