不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.
A
直接计算每一个选项最多对多少个题加起来即可。
时间复杂度为 \(O(n)\)。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
void read(int &x){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
read(x),read(vv...);
}
const int N=1000100;
int a[N];
signed main(){
int T=read();
while(T--){
string s;
int n;
cin>>n>>s;
s=' '+s;
int box[10]={0};
for(int i=1;i<=4*n;++i)
if(s[i]!='?')++box[s[i]-'A'];
int mx=0;
for(int i=0;i<4;++i)
mx+=min(box[i],n);
cout<<mx<<'\n';
}
}
B
这是 B?这不比 C 难?
首先如果一开始全部是奇数或者全部是偶数的话不需要操作。其他的时候一定是把所有的数都变成奇数。
然后贪心的找到最大的奇数 \(v\),把所有的偶数从小到大排序,令当前枚举到的偶数值为 \(w\):
- \(v\ge w\)。那么此时 \(w\leftarrow v+w\),有 \(2\not\mid w\)。\(w\) 变成新的最大的奇数,\(v\leftarrow w\)。
- \(v<w\)。那么此时 \(v\leftarrow v+w\),有 \(v>w\),随后 \(w\leftarrow v+w\),有 \(2\not\mid w\)。\(w\) 变成新的最大的奇数,\(v\leftarrow w\)。
但是上面的贪心策略其实是错误的。发现 \(v<w\) 的时候所有未取到的偶数均 \(\ge v\)。因此直接对做大的 \(w\) 做交换,剩下的全部变为 \(v\ge w\) 的情况。时间复杂度为 \(O(n\log n)\),瓶颈在于排序。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
void read(int &x){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
read(x),read(vv...);
}
const int N=1000100;
int a[N];
signed main(){
int T=read();
while(T--){
int n=read();
for(int i=1;i<=n;++i)a[i]=read();
int cnt=0;
for(int i=1;i<=n;++i)if(a[i]%2!=a[1]%2){cnt=1;break;}
if(!cnt)cout<<"0\n";
else{
sort(a+1,a+n+1);
int val;
for(int i=1;i<=n;++i)
if(a[i]&1)val=a[i];
int cnt=0;
for(int i=1;i<=n;++i)
if(~a[i]&1){
if(val>=a[i]){
++cnt;
a[i]+=val;
val=a[i];
}
else{
int p=n;
for(int j=n;j;--j)
if(~a[j]&1){
p=j;
break;
}
val+=a[p];
++cnt,++cnt;
a[p]+=val;
val=a[p];
--i;
}
}
cout<<cnt<<'\n';
}
}
}
C
对 \(a_i\bmod 2m\) 破换成链。则若某一段区间的极差不超过 \(m\) 则有解,否则无解。有解的部分取最大值。问题在于怎么计算最大值为多少。
可以发现大体上就是解一个方程组:
\[\left\{ \begin{aligned} &\quad x\ge \text{MAX}\\ &\quad x\equiv V_i(\bmod 2m) \end{aligned} \right. \]其中 \(\text{MAX}\) 表示所有 \(a_i\) 的最大值即所有芯片全部安装的最小时间,\(V_i\) 表示当前所枚举区间的终点。
求 \(x\) 的最小值可以:
\[\left\{ \begin{aligned} &\quad x\ge \text{MAX}\\ &\quad x+2Qm=V_i \end{aligned} \right. \]其中 \(Q\in\textbf{Z}\)。
方程可以解得 \(x_\text{min}=2m\times \lceil\frac{\text{MAX}-V_i}{2m}\rceil+V_i\)。直接带进去求最大值即可。
时间复杂度为 \(O(n\log n)\)。瓶颈同样在于排序。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
void read(int &x){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
read(x),read(vv...);
}
const int N=1000100;
int a[N];
signed main(){
int T=read();
while(T--){
int n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
vector<int>v;
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)v.pb(a[i]%(m+m));
sort(v.begin(),v.end());
int mx=*max_element(a+1,a+n+1);
int res=-1;
if(v.back()-v[0]<m){
//mod 2m 同余 v.back()
//且>=mx
res=max(res,((mx-v.back()+m+m-1)/(m+m))*(m+m)+v.back());
}
for(int i=1;i<v.size();++i){
//从v[i]到v[i-1]+m+m
int cho=v[i-1]+m+m-v[i]+1;
if(cho<=m){
//mod 2m 同余 v[i-1]
//且>=mx
res=max(res,((mx-v[i-1]+m+m-1)/(m+m))*(m+m)+v[i-1]);
// cout<<i-1<<": "<<(mx-v[i-1]+m+m-1)/(m+m)<<'\n';
// int rres=mx-v[i-1];
// rres=(rres+m+m-1)/(m+m);
// res=max(res,rres);
}
}
cout<<res<<'\n';
}
}
D
考虑经典套路二分答案 \(p\)。问题变为判定中位数为 \(p\) 是否可行。
考虑判定的时候 dp。定义 \(a_i\ge p\) 的时候 \(a_i\) 权值为 \(1\),否则权值为 \(-1\)。令 \(f_i\) 表示前 \(i\) 个元素权值之和最大是多少(需要在数量合法的前提下)。定义 \(V_i\) 表示 \(i\) 点权值。
因此有初始条件 \(f_0=0\)。然后考虑每一个 \(i\):若 \(i-1\equiv 0(\bmod k)\) 则此时不可以从前面一个元素转移过来,只能往前跳 \(k\) 个元素。因此有 \(f_i\leftarrow f_{i-k}\)。否则既可以往前跳 \(k\) 个元素也可以直接从上一个元素转移过来,有 \(f_i\leftarrow\max(f_{i-1}+V_i,f_{i-k})\)。只需要判定 \(f_n\) 是否 \(\ge 0\) 即可。时间复杂度为 \(O(n\log n)\)。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
using namespace std;
int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
void read(int &x){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
read(x),read(vv...);
}
const int N=1000100;
int a[N],n,k,f[N],g[N];
bool check(int p){
//需要有至少Q/2+1个数>=p
f[0]=0;g[0]=0;
int Q=n%k;if(!Q)Q=k;
// for(int i=1;i<=k;++i)g[i]=-1e9;
for(int i=1;i<=n;++i)f[i]=-1e9;
for(int i=1;i<=n;++i)if(a[i]>=p){
if((i-1)%k==0){
if(i-k>=0)f[i]=max(f[i-k],1);
else f[i]=1;
}else{
if(i-k>=0)
f[i]=max(f[i-1]+1,f[i-k]);
else
f[i]=f[i-1]+1;
}
}else{
if((i-1)%k==0){
if(i-k>=0)f[i]=max(f[i-k],-1);
else f[i]=-1;
}else{
if(i-k>=0)
f[i]=max(f[i-1]-1,f[i-k]);
else
f[i]=f[i-1]-1;
}
}
// for(int i=1;i<=n;++i)if(a[i]>=p){
// f[i]=g[(i-1+k)%k]+1;
// g[i%k]=max(g[i%k],f[i]);
// }
return f[n]>0;
}
signed main(){
int T=read();
while(T--){
n=read(),k=read();
for(int i=1;i<=n;++i)a[i]=read();
int l=1,r=1e9,best=-1;
while(l<=r){
int mid=l+r>>1;
if(check(mid))best=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",best);
}
}
F1
考虑忘了是哪一场远古 CF 的一个题套路,每 \(2w\) 行 \(2h\) 列即为一个循环。因此开一个 map 记录出第一次操作每一个位置走到过的次数。然后考虑枚举 \(k\) 次不同的走法。每一次直接使用公式计算出其所对应的起点并更新答案即可。
设第一次结束之后位于坐标 \((x,y)\) 那么第 \(i\) 轮的起点即为 \((-(i-1)x\bmod 2w,-(i-1)y\bmod 2h)\)。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
void read(int &x){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-w;
ch=getchar();
}
while(isdigit(ch))
s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
read(x),read(vv...);
}
const int N=1000100;
int a[N],n,k,f[N],g[N];
signed main(){
int T=read();
while(T--){
int n,k,w,h;read(n,k,w,h);
string s;cin>>s;
map<pair<int,int>,int>mp;
int x=0,y=0;
for(int i=0;i<n;++i){
if(s[i]=='L')--x;
else if(s[i]=='R')++x;
else if(s[i]=='U')++y;
else --y;
x=(x+w+w)%(w+w);
y=(y+h+h)%(h+h);
++mp[{x,y}];
}
int res=0;
for(int i=0;i<k;++i){
int _x=(-i*x%(w+w)+(w+w))%(w+w);
int _y=(-i*y%(h+h)+(h+h))%(h+h);
res+=mp[{_x,_y}];
}
cout<<res<<'\n';
}
}
标签:F1,ch,963,int,read,补题,define,getchar
From: https://www.cnblogs.com/yhbqwq/p/18342560