AC源Day7模拟赛复盘
MarkLikeFlorr · · 个人记录
单击此处添加标题
T1（75 TLE）：
纯模拟，但是我没写卡时代码导致痛失25pts。 ::::success[AC代码]
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n,j=1,f=1;
int p,cnt=0,num[N];
int type[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>p;
for(int i=1;i<=n;i++){
cin>>type[i]>>num[i];
}
while(p<=n && p>0){
if(type[p]==1 && j>=num[p]){
cnt++;
type[p]=(-1);
}
else if(type[p]==0){
j+=num[p];
f*=(-1);
}
if((double)clock()/CLOCKS_PER_SEC > 1.9){
cout<<cnt;
return 0;
}
p+=j*f;
}
cout<<cnt;
return 0;
}::::
T2（100 AC）
二分查找符合条件的棚子看数量满不满足要求。（注意离散化一下就可以了） ::::success[AC代码]
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,m;
int t[N],s[N],cnt=0;
vector<int> v;
map<int,int> mp;
int search(int u,int l,int r){
if(v[n]<u) return n+1;
if(l==r) return l;
int mid=(l+r)/2;
if(u==v[mid]) return mid;
else if(u>v[mid]) return search(u,mid+1,r);
else return search(u,l,mid);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t[i];
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
t[i]-=x+1;
}
for(int i=1;i<=n;i++) mp[t[i]]++;
v.push_back(-1);
for(auto i:mp){
if(i.first<0) continue;
v.push_back(i.first);
cnt++;
}
n=cnt;
for(int i=n;i>=1;i--){
s[i]=s[i+1]+mp[v[i]];
}
for(int i=1;i<=m;i++){
int tmp,v;
cin>>v>>tmp;
if(s[search(tmp,1,n)]>=v) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}::::
T3（48 WA）
要使疫病开始时的感染人数更小，需要让疫病持续天数尽可能地长，然后再来反推开始感染了多少鼠/牛。 ::::warning[48代码]
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,m;
int t[N],s[N],cnt=0;
vector<int> v;
map<int,int> mp;
int search(int u,int l,int r){
if(v[n]<u) return n+1;
if(l==r) return l;
int mid=(l+r)/2;
if(u==v[mid]) return mid;
else if(u>v[mid]) return search(u,mid+1,r);
else return search(u,l,mid);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t[i];
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
t[i]-=x+1;
}
for(int i=1;i<=n;i++) mp[t[i]]++;
v.push_back(-1);
for(auto i:mp){
if(i.first<0) continue;
v.push_back(i.first);
cnt++;
}
n=cnt;
for(int i=n;i>=1;i--){
s[i]=s[i+1]+mp[v[i]];
}
for(int i=1;i<=m;i++){
int tmp,v;
cin>>v>>tmp;
if(s[search(tmp,1,n)]>=v) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}:::: ::::success[AC代码]
#include<bits/stdc++.h>
#define int long long
#define N 300005
#define mamba return
#define out 0
using namespace std;
const int w=300005;
int n,maxn=0x3f3f3f3f,vn;
bool now[N];
string cinn;
vector<int> t;
void init(){
int cnt=0;
for(int i=1;i<=n+1;i++){
if(now[i]) cnt++;
else if(cnt>0){
t.push_back(cnt);
cnt=0;
}
}
vn=t.size()-1;
}
int max_moon(int u,int p){
if(u==0) return 0x3f3f3f3f;
if((p==1 && now[1]) || (p==vn && now[n])){
return u-1;
}
else{
if(u%2==0) u--;
return u/2;
}
}
int check(int u,int d){
if(u==0) return 0;
if(d==0) return u;
int l=1,r=u,minn=0x3f3f3f3f;
while(l<r){
int mid=(l+r)/2;
if(mid+mid*d*2>=u){
minn=min(minn,mid);
r=mid;
}
else{
l=mid+1;
}
}
return minn;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>cinn;
t.push_back(0);
for(int i=0;i<n;i++){
now[i+1]=(cinn[i]=='1');
}
init();
if(vn==0){
cout<<0;
return 0;
}
for(int i=1;i<=vn;i++){
maxn=min(maxn,max_moon(t[i],i));
}
int ans=0;
for(int i=1;i<=vn;i++){
ans+=check(t[i],maxn);
}
cout<<ans;
mamba out;
}::::
T4（骗分）：
考虑最坏的情况，即为：
- 若A选择奇数，则B一定会选偶数的最大值，没有也会选奇数的最小值。
- 若A选择偶数，则同理B一定会选奇数最大或偶数最小。
状态设计：
dp[i][0/1]为最后一次是奇数/偶数时可以得到的最大价值。
注意到有负数，所以状态转移方程为：
dp[i][0] = min(0,max(dp[i + 1][0],dp[i + 1][1])) + o[i] dp[i][1] = min(0,max(dp[i + 1][0],dp[i + 1][1])) + e[i]
代码仍在施工中~
T5（骗分）：
线性暴力DP，设dp[i][j]是考虑前搂住抓住的最小代价，枚举改变的断点，求出最小代价。
代码仍在施工中~
T6（骗分）：
设dp[i]为前i项的答案，可以枚举x（刷红蓝的长度）进行转移，但会到
正解不会写