题目传送门

A 小K的疑惑

B Milk Measurement

C Stack in a rut

D Air Cownditioning II

T1小K的疑惑

思路

公式是 (a-1)*(b-1)-1，如有疑问请自行打表

代码

#include<bits/stdc++.h>
 using namespace std;
 int main(){
     freopen("dontforgetfileio.in","r",stdin);
     freopen("dontforgetfileio.out","w",stdout);
     long long a,b;
     cin>>a>>b;
     cout<<(b-1)*(a-1)-1;
 }

T2 Milk Measurement

思路

直接一天天的算就行了，如果有变动则更新并计数

代码

#include<bits/stdc++.h>
 using namespace std;
 int a=1,b=1,c=1,cn;
 int st[1111][10];
 int main(){
     freopen("milk2.in","r",stdin);
     freopen("milk2.out","w",stdout);
     int n;
     cin>>n;
     for(int i=1;i<=n;i++){
         int day,l;
         string m,xx;
         cin>>day;
         cin>>m;
         cin>>xx;
         int x=0;
         for(int i=1;i<xx.size();i++)x=x*10+xx[i]-'0';
         l=x;
         if(xx[0]=='-')l=-l;
         if(m[0]=='B')st[day][1]+=l;
         if(m[0]=='E')st[day][2]+=l;
         if(m[0]=='M')st[day][3]+=l;
     }
     int aaa=7,bbb=7,ccc=7;
     for(int i=1;i<=100;i++){
         aaa+=st[i][1];
         bbb+=st[i][2];
         ccc+=st[i][3];
         int x=aaa,y=bbb,z=ccc;
         int aa=0,bb=0,cc=0,m=max(x,max(y,z));
         if(x==m)aa=1;
         if(y==m)bb=1;
         if(z==m)cc=1;
         if(aa!=a||bb!=b||cc!=c){
             cn++;
             a=aa;
             b=bb;
             c=cc;
         }
     }
     cout<<cn;
 }

T3 Stack in a rut

思路

两个点p(E),q(N),要满足p.x<q.x&&p.y>q.y p排序用x排，q排序用y排 p点到相交点的距离是p.x-q.x p点到相交点的距离是p.y-q.y 注意一个(p/q)点可能会被提前的其他点拦截

代码

#include<bits/stdc++.h>
 using namespace std;
 int aa,bb,da[10000],dd[10000],n;
 struct P{
     int x,y,id;
 }a[1000],b[1000];
 bool cmp1(P a,P b){
     return a.y<b.y;
 }
 bool cmp2(P a,P b){
     return a.x<b.x;
 }
 int main(){
     freopen("stack.in","r",stdin);
     freopen("stack.out","w",stdout);
     cin>>n;
     for(int i=1;i<=n;i++){
         char x;
         cin>>x;
         if(x=='N'){
             aa++;
             cin>>a[aa].x>>a[aa].y;
             a[aa].id=i;
         }
         else{
             bb++;
             cin>>b[bb].x>>b[bb].y;
             b[bb].id=i;
         }
         
     }
     sort(a+1,a+1+aa,cmp1);
     sort(b+1,b+1+bb,cmp2);
     for(int i=1;i<=aa;i++){
         int xx=a[i].x,yy=a[i].y;
         int h=1000000000;
         for(int j=1;j<=bb;j++){
             int x=b[j].x,y=b[j].y;
             if(x<xx&&y>yy){
                 int jb=abs(a[i].x-b[j].x);
                 int ib=abs(a[i].y-b[j].y);
                 if(ib>jb){
                     h=min(h,ib);
                 }
             }
         }
         da[a[i].id]=h;
     }
     for(int i=1;i<=bb;i++){
         int x=b[i].x,y=b[i].y;
         int h=1000000000;
         for(int j=1;j<=aa;j++){
             int xx=a[j].x,yy=a[j].y;
             if(x<xx&&y>yy){
                 int ib=abs(b[i].x-a[j].x);
                 int jb=abs(b[i].y-a[j].y);
                 if(ib>jb&&jb<=da[a[j].id]){
                     h=min(h,ib);
                 }
             }
         }
         dd[b[i].id]=h;
     }
     for(int i=1;i<=bb;i++){
         int x=b[i].x,y=b[i].y;
         int h=1000000000;
         for(int j=1;j<=aa;j++){
             int xx=a[j].x,yy=a[j].y;
             if(x<xx&&y>yy){
                 int ib=abs(b[i].x-a[j].x);
                 int jb=abs(b[i].y-a[j].y);
                 if(ib>jb){
                     h=min(h,ib);
                 }
             }
         }
         da[b[i].id]=h;
     }
     for(int i=1;i<=aa;i++){
         int xx=a[i].x,yy=a[i].y;
         int h=1000000000;
         for(int j=1;j<=bb;j++){
             int x=b[j].x,y=b[j].y;
             if(x<xx&&y>yy){
                 int jb=abs(a[i].x-b[j].x);
                 int ib=abs(a[i].y-b[j].y);
                 if(ib>jb&&jb<=da[b[j].id]){
                     h=min(h,ib);
                 }
             }
         }
         dd[a[i].id]=h;
     }
     for(int i=1;i<=n;i++){
         if(dd[i]==1000000000)cout<<"Infinity";
         else cout<<dd[i];
         cout<<"\n";
     }
 }

错误与感想

考试的时候直接骗分，再写的时候细节有点没注意

以后考试时没写题目要多想一下，细节也要注意

T4 Air Cownditioning II

思路

DFS搜索，对于每一步，遍历[1,100]，记录情况，再看是否满足要求，满足则更新

代码

#include<bits/stdc++.h>
 using namespace std;
 int n,m,a[1000],b[1000],mq=1000000;
 struct P{
     int x,y,p,q;
 }k[1000];
 void dfs(int w,int q,int s){
     if(s==0){
         mq=min(mq,q);
         return;
     }
     if(w>m&&s!=0)return;
     dfs(w+1,q,s);
     for(int l=k[w].x;l<=k[w].y;l++)b[l]+=k[w].p;
     int ss=0;
     for(int i=1;i<=100;i++)if(b[i]>=a[i])ss++;
     ss=100-ss;
     dfs(w+1,q+k[w].q,ss);
     for(int l=k[w].x;l<=k[w].y;l++)b[l]-=k[w].p;
 }
 int main(){
     freopen("air.in","r",stdin);
     freopen("air.out","w",stdout);
     cin>>n>>m;
     for(int i=1;i<=n;i++){
         int x,y,w;
         cin>>x>>y>>w;
         for(int j=x;j<=y;j++)a[j]=w;
     }
     for(int i=1;i<=m;i++)cin>>k[i].x>>k[i].y>>k[i].p>>k[i].q;
     dfs(1,0,100);
     cout<<mq;
 }

错误与感想

比赛时随机数骗分，还居然没看出是****搜索题！！！太对不起搜索之子的称号了·

以后要积极写题，特别是****搜索题