Codeforces Round #690 (Div. 3)
A:水题，根据题目意思模拟即可
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int st[10005],prime[10005],cnt;
int vis[105];
int a[305];
void ola()
{
for(int i=2;i<=1000000;i++)
{
if(st[i]==0) prime[cnt++]=i;
for(int j=0;j<=cnt&&j*prime[i]<=1000000;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans % mod;
}
int main()
{
ios::sync_with_stdio;
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--)
{
int n; cin >> n;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++) cin >> a[i];
int k=n;
int cnt=1;
int tmp=1;
while(tmp<=n)
{
if(tmp%2) cout << a[cnt++] <<" ";
else cout << a[k--] << " ";
tmp++;
}
cout << endl;
}
return 0;
} B：删除一段连续字符判断剩下的是否是“2020”，YES就6种情况 #include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int st[10005],prime[10005],cnt;
int vis[105];
int a[305];
void ola()
{
for(int i=2;i<=1000000;i++)
{
if(st[i]==0) prime[cnt++]=i;
for(int j=0;j<=cnt&&j*prime[i]<=1000000;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans % mod;
}
int main()
{
ios::sync_with_stdio;
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--)
{
int n; cin >> n;
string s; cin >> s;
if (s == "2020" ||(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[3]=='0')||(s[0] == '2' && s[n - 1] == '0' && s[n - 2] == '2' && s[n - 3] == '0') ||(s[0] == '2' && s[1] == '0' && s[n - 2] == '2' && s[n - 1] == '0') ||(s[0] == '2' && s[1] == '0' && s[2] == '2' && s[n - 1] == '0')||(s[n-1]=='0'&&s[n-2]=='2'&&s[n-3]=='0'&&s[n-4]=='2')) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
} C：输入一个数X，问x最小能用哪个数上的每位数之和（每位数不相同）表示，如果没有这样的数输出-1. 如果x大于45直接输出-1，优先取0~9中大的数这样保证数的位数最小，然后排序输出 #include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int st[10005],prime[10005],cnt;
int vis[105];
int a[305];
void ola()
{
for(int i=2;i<=1000000;i++)
{
if(st[i]==0) prime[cnt++]=i;
for(int j=0;j<=cnt&&j*prime[i]<=1000000;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans % mod;
}
int main()
{
ios::sync_with_stdio;
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--)
{
int x; cin >> x;
vector<int>v;
int cnt=9;
while (x >= 10&&cnt)
{
v.push_back(cnt);
x -= cnt--;
}
if(x>45) cout << -1 << endl;
else if(x)
{
int tmp=(1+cnt)*cnt/2;
if (x>tmp) cout << -1 << endl;
else
{
int temp=cnt;
while(x != 0)
{
if (x >= temp) v.push_back(temp), x -= temp;
temp--;
}
sort(v.begin(), v.end());
vector<int>::iterator it = v.begin();
for(; it != v.end(); ++it)
{
cout<<(*it);
}
cout << endl;
}
}
}
return 0;
} D：一个数组，每次能让ai加到a(i+1)或者a(i-1),问最少多少次让数组中元素都相等。最后数组元素之和sum肯定不变，且每个元素都是sum的因子，那筛出sum的所有因子，从小到大模拟一遍即可。 #include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int st[10005],prime[10005],cnt;
int vis[105];
ll a[3005];
void ola()
{
for(int i=2;i<=1000000;i++)
{
if(st[i]==0) prime[cnt++]=i;
for(int j=0;j<=cnt&&j*prime[i]<=1000000;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans % mod;
}
int main()
{
ios::sync_with_stdio;
cin.tie(0);cout.tie(0);
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
memset(a,0,sizeof(a));
ll sum=0;
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
sum+=a[i];
}
vector<ll>v;
for(ll i=1;i*i<=sum;i++)
{
if(sum%i==0)
{
v.push_back(i);
if(i*i!=sum) v.push_back(sum/i);
}
}
sort(v.begin(),v.end());
ll flag1=1,flag2=0;
for(ll i=0;i<v.size();i++)
{
ll summ=0;
flag1=1;
for(ll j=1;j<=n;j++)
{
summ+=a[j];
if(summ==v[i]) summ=0;
if(summ>v[i])
{
flag1=0;
break;
}
}
if(flag1)
{
cout << n-sum/v[i] << endl;
flag2=1;
break;
}
}
if(flag2==0) cout << n-1 << endl;
}
return 0;
}
E1：从n各数中选三个数，保证三个数中最大值减最小值小于等于2。排序+lower_bound。从第三个数开始遍历，每次去找比这个数小2的数，得到位置，即可通过组合数算出。 别用memset初始化，开始没注意，一直tle9，删了秒过
2020/12/21
#include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int st[10005],prime[10005],cnt;
int vis[105];
ll a[200005];
void ola()
{
for(int i=2;i<=1000000;i++)
{
if(st[i]==0) prime[cnt++]=i;
for(int j=0;j<=cnt&&j*prime[i]<=1000000;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans % mod;
}
int main()
{
ios::sync_with_stdio;
cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--)
{
ll n; cin >> n;
for(ll i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+1+n);
ll ans=0;
for(ll i=3;i<=n;i++)
{
ll pos=lower_bound(a+1,a+1+n,a[i]-2)-a;
ll t=i-pos;
if(t<2) continue;
else
{
ans+=(t-1)*(t)/2;
}
}
cout << ans << endl;
}
return 0;
}
要下课了，剩下E2和F抽时间再写吧2020/12/21
E2 题目意思和E1一样就是没限定m和k，再加个取模。费马小定理求逆元+组合数，也可以用lucas。
#include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
int st[10005],prime[10005],cnt;
int vis[105];
ll a[200005];
ll fac[200005],inv[200005];
void ola()
{
for(int i=2;i<=1000000;i++)
{
if(st[i]==0) prime[cnt++]=i;
for(int j=0;j<=cnt&&j*prime[i]<=1000000;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans % MOD;
}
void init()
{
fac[0]=inv[0]=1;
for(int i=1;i<200005;i++)
{
fac[i]=(fac[i-1]*i)%MOD;//求阶乘
inv[i]=qpow(fac[i],MOD-2);//费马小定理求逆元
}
}
ll C(ll a,ll b)
{
if(a<b||b<0) return 0;
return (fac[a]*inv[b]%MOD)*inv[a-b]%MOD;
}
int main()
{
ios::sync_with_stdio;
cin.tie(0);cout.tie(0);
int t; cin >> t;
init();
while(t--)
{
int n,m,k; cin >> n >> m >> k;
for(int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+1+n);
ll ans=0;
int l=1;
for(int r=m;r<=n;r++)
{
while(a[r]-a[l]>k) l++;//a[l]太小
if(r-l+1<m) continue;//不够m个数
ans=(ans+C(r-l,m-1))%MOD;//确定当前最大值为a[r]，再从剩下的[l,r-1]（即r-1-l+1=r-l）取m-1个数
}
cout << ans << endl;
}
return 0;
} F：给你n个二元组，代表线段的左右端点，问最少删几条线段，使得剩下当中存在一个线段与所有剩下的所有线段都有交集。最多删除n-1次，我们要删除的线段是它的右端点比当前该线段左端点小，左端点比当前线段右端点大。二分左端点和右端点。每次比较取最小值即可。 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10005;
const int N = 200005;
int st[MAXN+5],prime[MAXN+5],cnt;
/*void ola()
{
for(int i=2;i<=MAXN;i++)
{
if(!st[i]) prime[cnt++];
for(int j=0;j<=cnt&&i*prime[j]<=MAXN;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]) break;
}
}
}
ll gcd(ll a, ll b)
{
return b==0?a:gcd(b,a%b);
}*/
pair<int,int>p[N];
int ls[N],rs[N];
int main()
{
//ios::sync_with_stdio;
//cin.tie(0);cout.tie(0);
int t; cin >> t;
while(t--)
{
int n; cin >> n;
for(int i=1;i<=n;i++)
{
int l,r; cin >> l >> r;
p[i]=make_pair(l,r);
ls[i]=l; rs[i]=r;
}
sort(ls+1,ls+1+n);
sort(rs+1,rs+1+n);
ll ans = n-1;
for(int i=1;i<=n;i++)
{
ll dl=lower_bound(rs+1,rs+1+n,p[i].first)-rs-1;
ll dr=ls+n+1-upper_bound(ls+1,ls+1+n,p[i].second);
ans = min(ans, dl+dr);
}
cout << ans << endl;
}
return 0;
} 
投递巨人网络等公司6个岗位 >
查看9道真题和解析