\(D1T1\) 均分纸牌 \((OK)\)

\(D1T2\) 字串变换 \((OK)\)

\(D1T3\) *落体 \((OK)\)

\(D1T4\) 矩形覆盖 \((OK)\)

这年的题其实题目很好,但是数据点又少还水.

\(T1\)贪心模拟入门题.最终每一堆纸牌的数量是已知的,即\(ave=\frac{sum}{n}\).那么把每一堆纸牌数量减去\(ave\)后,如果为负数则要从别人那里拿纸牌,如果为正数就要给别人纸牌,如果为\(0\)就不要动.按照这样从左往右模拟即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=105;
int a[N];
int main(){
    int n=read(),sum=0,ans=0;
    for(int i=1;i<=n;++i)a[i]=read(),sum+=a[i];
    int ave=sum/n;for(int i=1;i<=n;++i)a[i]-=ave;
    for(int i=1;i<n;++i){
        if(a[i]!=0)++ans,a[i+1]+=a[i];
    }
    printf("%d\n",ans);
    return 0;
}

\(T2\)字符串做到崩溃.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
int num=1;
string st,ed,turna[10],turnb[10];
map<string,int>Map;queue<string>q;
inline bool bfs(){
    Map[st]=1;q.push(st);
    while(q.size()){
        string u=q.front();q.pop();
        for(int i=1;i<=num;++i){
            string now=u;
            while(1){
                int pos=now.find(turna[i]);
                if(pos==-1)break;
                string v=u;now[pos]='|';
                v.replace(pos,turna[i].size(),turnb[i]);
                if(Map[v])continue;
                Map[v]=Map[u]+1;
                if(v==ed)return true;
                if(Map[v]>=11)return false;
                q.push(v);
            }
        }
    }
    return false;
}
int main(){
    cin>>st>>ed;while(cin>>turna[num]>>turnb[num])num++;num--;
    int pd=bfs();if(pd)printf("%d\n",Map[ed]-1);else puts("NO ANSWER!");
    return 0;
}

\(T3\)蒟蒻只会中规中矩的一个一个点枚举,然后判断能否被接到.反正应该是数据水的原因,只错了一个点,然后就不会做了.然后题解里面全都是\(O(1)\)的神仙做法,发现反而更好理解:就是说每个小球都是同时下落,同时落地的,那么设小球落到车顶\(h-k\)的时间为\(tmin\),落到地上\(h\)的时间为\(tmax\),那么根据小车的速度和车长,可以把小车看做是有这么一段区间,小球的下落位置的横坐标如果在区间内就能被接到.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
double h,s,v,l,k;int n;
int main(){
    scanf("%lf%lf%lf%lf%lf%d",&h,&s,&v,&l,&k,&n);
    double tmin=sqrt((h-k)/5),tmax=sqrt(h/5);
    int imin=(int)(s-tmax*v),imax=(int)(s-tmin*v+l);
    printf("%d\n",min(imax,n)-max(0,imin));
    return 0;
}

\(T4\)这道题我本来觉得很难的,然后随便打了个搜索+剪枝就过了.肯定是数据太水了.我自己是这么想的:把所有点按照横坐标从小到大排序后,最优方案中一个矩形覆盖到的肯定是一段连续的点(这个贪心显然是错的,我虽然造不出\(hack\)数据,但我就觉得这个贪心是错的,因为如果有两个点横坐标相距很远,但是纵坐标一样,那么用一个矩形覆盖这两个点产生的贡献是\(0\),很优).

然后就直接搜索枚举每个矩形覆盖哪一段连续的点即可.再加上一个最优性剪枝,跑得飞快.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=51;
int n,k,ans=1<<30;
struct node{int x,y;}a[N];
inline bool cmp(node x,node y){return x.x==y.x?x.y<y.y:x.x<y.x;}
inline void dfs(int now,int cnt,int sum){
    if(sum>=ans)return;
    if(now>n){ans=sum;return;}
    if(cnt>k)return;    
    for(int i=now;i<=n;++i){
        int xmin=1<<30,xmax=0,ymin=1<<30,ymax=0;
        for(int j=now;j<=i;++j){
            xmin=min(xmin,a[j].x);
            xmax=max(xmax,a[j].x);
            ymin=min(ymin,a[j].y);
            ymax=max(ymax,a[j].y);
        }
        dfs(i+1,cnt+1,sum+(xmax-xmin)*(ymax-ymin));
    }
}
int main(){
    n=read();k=read();
    for(int i=1;i<=n;++i)a[i].y=read(),a[i].x=read();   
    sort(a+1,a+n+1,cmp);
    dfs(1,1,0);printf("%d\n",ans);
    return 0;
}