- chenshixian 的博客
陈室先的总结7.16day8
-
chenshixian
LV 2
@
2024-7-17 18:59:09
题目传送门
T1. 小田的同余😄
思路❤️
要开long long，直接输出符合条件的“（m+1）/2”就可以了
代码🎉️
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("mod.in","r",stdin);
freopen("mod.out","w",stdout);
long long m;
cin>>m;
cout<<(m+1)/2;
}
T2. 小田的奶牛要饿坏啦！！
思路
我们发现绝对不能枚举天数，所以我们可以在输入时进行模拟，算出能吃几天
代码🎉️
#include<bits/stdc++.h>
using namespace std;
long long n,t,q=-1,z=-1,l=0;
struct P{
long long d,b;
}a[100010];
long long c;
int main(){
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>a[i].d>>a[i].b;
if(l)continue;
if(a[i].d>z)q=-1,z=-1;
c+=a[i].b;
if(q==-1)q=a[i].d;
if(z!=-1)z=z+a[i].b;
if(z==-1)z=a[i].d+a[i].b-1;
if(z>t)c-=(z-t),l=1;
}
cout<<c;
}
T3小田喂猫😥🤕
错的点😱
1.我用了暴力，拿了50分，以后要多多优化
👌思路
用们可以发现这一段可以分成两段，一段是小于k的，用原价是，另一段大于k，价值用k,数量用原本，然后我们可以用两个前缀和辅助
🍗代码
#include<bits/stdc++.h>
using namespace std;
long long n,q,k;
struct P{
long long a,b,c,d;
}a[100010];
bool cmp(P a,P b){
return a.b<=b.b;
}
int main(){
freopen("cat.in","r",stdin);
freopen("cat.out","w",stdout);
cin>>n;
for(long long i=1;i<=n;i++)cin>>a[i].a;
for(long long i=1;i<=n;i++)cin>>a[i].b;
sort(a+1,a+1+n,cmp);
for(long long i=1;i<=n;i++)a[i].c=a[i-1].c+a[i].a*a[i].b;
for(long long i=n;i>=1;i--)a[i].d=a[i+1].d+a[i].a;
cin>>q;
a[0].b=-100;
while(q--){
cin>>k;
long long l=0,r=n;
while(l<r){
long long m=(l+r+1)>>1;
if(a[m].b<=k)l=m;
else r=m-1;
}
cout<<a[l].c+k*a[l+1].d<<"\n";
}
}
T4小田的打字练习😎😏
👾错的点
1.我直接骗分的，以后有时间这种大模拟一定要写
🤩思路
这是一道模拟，我么可以用循环处理模板与小田的，然后再对比，把一样的字符加到计数变量里，最后算速度
代码🙃
#include <bits/stdc++.h>
using namespace std;
vector<string> mb,xt;
int main(){
freopen("key.in","r",stdin);
freopen("key.out","w",stdout);
string sr;
while(getline(cin,sr)&&sr!="EOF"){
if(sr=="")continue;
vector<char>cz;
for(int i=0;i<sr.size();i++){
if(sr[i]=='<'&&cz.size()) cz.pop_back();
if(sr[i]!='<')cz.push_back(sr[i]);
}
string cl;
for(int i=0;i<cz.size();i++) cl+=cz[i];
if(cl.size()!=0)mb.push_back(cl);
}
while(getline(cin,sr)&&sr!="EOF"){
if(sr=="")continue;
vector<char>cz;
for(int i=0;i<sr.size();i++){
if(sr[i]=='<'&&cz.size())cz.pop_back();
if(sr[i]!='<')cz.push_back(sr[i]);
}
string cl;
for(int i=0;i<cz.size();i++) cl+=cz[i];
if(cl.size()!=0)xt.push_back(cl);
}
double sj,js=0;
cin>>sj;
for(int i=0;i<mb.size()&&i<xt.size();i++)for(int j=0;j<mb[i].size()&&j<xt[i].size();j++)if(mb[i][j]==xt[i][j])js++;
cout<<(long long)((60/sj*js)+0.5);
}
T5小田切蛋糕😴🤐
错的地方😤
1.纯骗分，以后要多思考
思路👿
我们可以枚举个数，再计算是否可行，所以可以用前缀和写，但会超时，所以还要二分来找个数
代码🎁
#include<bits/stdc++.h>
using namespace std;
int d[5555][5555],s[5555][5555],a,b,r,c,h;
int ch(int x){
int ro=0,c1=0;
for(int i=1;i<=r;i++){
int co=0,c2=0;
for(int j=1;j<=c;j++){
int t=s[i][j]-s[i][co]-s[ro][j]+s[ro][co];
if(t>=x)co=j,c2++;
if(c2==b){c1++,ro=i;break;}
}
if(c1==a)return 1;
}
return 0;
}
int main(){
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
cin>>r>>c>>a>>b;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>d[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+d[i][j];
if(i==r&&j==c)h=s[i][j];
}
}
int l=0,r=h;
while(l<r){
int m=(l+r+1)>>1;
if(ch(m))l=m;
else r=m-1;
}
cout<<l;
}
T6小田想困住奶牛😑👹
错的点💀
1.直接输出了-1，以后不能只骗分，要多打草稿
思路😜
我么可以用两个循环，一个奶牛向左冲，另一个向右冲，向左冲需要尽量向右走，向右冲需要尽量向左走，然后算需要的草，但如果冲出边界，那么结束循环
😃代码
#include<bits/stdc++.h>
using namespace std;
struct P{
int d,w;
}a[100010];
bool cmp(P a,P b){
return a.w<b.w;
}
int main(){
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
int n,m,p=1,dd,dx,l=dx,r=dd;
int an=1000000000;
cin>>n>>m;
for(int i=1;i<=n;i++){cin>>a[i].d>>a[i].w;}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
if(m<a[1].w||m>a[n].w){cout<<-1;return 0;}
for(int i=1;i<=n;i++)if(p&&a[i].w>m)dd=i,dx=i-1,p=0;
l=dx,r=dd;
while(l>=1){
while(a[r].w-a[l].w>a[r].d&&r<=n)r++;
if(r>n)break;
an=min(an,a[r].w-a[l].w-a[l].d);
l--;
}
l=dx,r=dd;
while(r<=n){
while(a[r].w-a[l].w>a[l].d&&l>=1)l--;
if(l<1)break;
an=min(an,a[r].w-a[l].w-a[r].d);
r++;
}
if(an==1000000000)cout<<-1;
else cout<<max(an,0);
}