Noip 2019 冲刺

多做几套模拟题，体会心路历程。

二

from hzwer模拟赛整理 2014-9-6 NOIP模拟赛
time 08.16
准备拿出 3.5h 做这套题，可是做了 1.5h 就已经完全没有做下去的欲望了。

T1 工资

聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）
聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）
输入
第一行 2个数 n,m
接下来n行，每行一个数，代表Vi.
输出
最小的最大钱数。
数据范围
20% 1<=n<=20
另 20% 1<=n<=50,Vi的和不超过1000
100% 1<=n<=100,000,m<=n,Vi<=10,000

算法分析：
最大值最小，二分答案。
刚刚好，2015年的noip就考了二分答案的题
所以可能这道题在当年应该比现在更有思维难度。

得分分析：
大概在 2min 内得到此题的完整思路，在 10min 左右可以写完代码，在 15min 左右调试完毕。在 45min 左右写完暴力，在 60min 左右拍上。
写暴力的时间比写正解的时间要慢上 30min 是十分正常的，对于这种题目来说。

代码：

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
int n, m, a[N];
bool See(int x) {
    int use = 0;
    for(int i = 1; i <= n; i ++) {
        int j = i, now = 0;
        while(now + a[j] <= x && j <= n) {
            now += a[j];
            j ++;
        }
        i = j - 1;
        use ++;
    }
    return use <= m;
}
int main() {
    n = read(), m = read();
    int L = 0, R = 1e9, Ans;
    for(int i = 1; i <= n; i ++) a[i] = read();
    for(int i = 1; i <= n; i ++) L = max(L, a[i]);
    while(L <= R) {
        int mid = (L + R) >> 1;
        if(See(mid)) Ans = mid, R = mid - 1;
        else L = mid + 1;
    }   
    cout << Ans;
    return 0;
}

T2藏妹子之处

今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：
（1）任意两个单元格都不在同一行。
（2）任意两个单元格都不在同一列。
选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少。
答案模1000000007。所谓的两种不同方案是指：只要它选中的单元格有一个不同，就认为是不同的方案。
输入格式：
一行，4个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。

算法分析
题解
from https://www.cnblogs.com/zhber/p/4036003.html
2、发现对于三个点(x1,y1)(x2,y2)(x3,y3)，如果任意交换坐标费用不变，即如果换成(x2,y1)(x3,y2)(x1,y3)费用不变
所以题意=枚举3个横坐标和三个纵坐标，算合理的方案数
对于x1,x2,x3 , y1,y2,y3，若有x1 不妨令x1 枚举x1,y1,令s=2(x1+y1)则满足 minT<=2(x3-x1)+2(y3-y1)<=maxT 即(minT+s)/2<=x3+y3<=(maxT+s)/2的(x3,y3)才可以。则(x3,y3)对答案的更新即是(x2,y2)的个数，即(x3-x1-1)(y3-y1-1).这样枚举两个点n^4、TLE……
3、限定x3=k,则(minT+s)/2-k<=y3<=(maxT+s)/2-k.且y1+2<=y3<=c.
第三个点(k,???)对答案的更新是(k-x1-1)Σ[(minT+s)/2-k-y1-1到(maxT+s)/2-k-y1-1]
令S=(minT+s)/2-y1-1,T=(maxT+s)/2-k-y1-1,则对于x3=k,方案是(k-x1-1)Σ[S-k到T-k]=(k-x1-1)(S-T+1)(S+T-2k)
这样枚举x1,y1,x3，效率n^3、TLE……
4、其实这题跟CQOI2014数三角形很像。(x1,y1)和(x3,y3)构成一个矩形，但是对于一个确定的矩形边框，它的费用是一定的，就是2(x3-x1)+2(y3-y1)即矩形的边长。它对答案的贡献也是一定的，即(x3-x1-1)(y3-y1-1)。这个矩形在r*c的大矩形中出现的次数也是给定的，设矩形长为x,宽为y，则出现了(r-x+1)*(c-y+1)次。那么直接枚举矩形的边长，然后就可以算出答案。这样n^2

得分分析：
5min 20分

代码

#include<cstdio>
#include<iostream>
#define mod 1000000007
#define LL long long
using namespace std;
LL ans;
int n, m, mx, mn;
int main() {
    scanf("%d %d %d %d", &n, &m, &mn, &mx);
    for (int i = 3; i <= n; i ++)
        for (int j = 3; j <= m; j ++) {
            int w = 2 * (i + j - 2);
            if (w <= mx && w >= mn) ans += (LL) (n - i + 1) * (m - j + 1) * (i - 2) * (j - 2) % mod;
        }
    printf("%lld\n", (ans * 6) % mod);
}

T3银河之星

给定初始状态的多枚棋子，每次可以将一枚棋子向八个方向走两个或者走一个，跨过的棋子被消掉，问是否可以只剩下一枚棋子并且该棋子可以到达指定的位置。
棋盘大小 100 *100
初始棋子数目 10

算法分析：
不会做
没题解
凉凉

得分分析：
这种题这不知道该怎么办
暴力都不知道咋写或者说懒得写或者说写也不应定能写出来。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
map<ll,int> q;
ll bin[15],bg,ed;
int ans[1005];
int k,n,m,xt,yt,sz;
int xx[4]= {0,1,1,1},yy[4]= {1,-1,0,1};
bool mp[10][10];
void add(int x1,int y1,int x2,int y2) {
    x1=(x1+3)%3;
    x2=(x2+3)%3;
    y1=(y1+3)%3;
    y2=(y2+3)%3;
    int u=x1*3+y1,v=x2*3+y2;
    mp[u][v]=1;
}
void pre() {
    int a1,a2,b1,b2;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            for(int k=0; k<4; k++) {
                a1=i+xx[k],b1=j+yy[k];
                a2=a1+xx[k],b2=b1+yy[k];
                if(a2+xx[k]<n&&b2+yy[k]<m)add(i,j,a2,b2);
                if(a2<n&&b2<m)add(i,j,a1,b1);
            }
}
int dfs(ll x) {
    if(x==ed)return 1;
    int a,b,a1,a2,b1,b2,t;
    if(q[x])t=q[x];
    else t=q[x]=++sz;
    if(ans[t])return ans[t];
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) {
            int t=i*3+j;
            if(x/bin[t]%11)
                for(int k=0; k<4; k++) {
                    a1=(i+xx[k]+3)%3,b1=(j+yy[k]+3)%3;
                    a2=(a1+xx[k]+3)%3,b2=(b1+yy[k]+3)%3;
                    a=a1*3+b1,b=a2*3+b2;
                    if((x/bin[a]%11)&&mp[t][a])
                        if(dfs(x-bin[t]-bin[a]+bin[b])==1)return ans[t]=1;
                    if((x/bin[b]%11)&&mp[t][b])
                        if(dfs(x-bin[t]-bin[b]+bin[a])==1)return ans[t]=1;
                }
        }
    return ans[t]=-1;
}
int main() {
    freopen("galaxy.in","r",stdin);
    freopen("galaxy.out","w",stdout);
    bin[0]=1;
    for(int i=1; i<=10; i++)bin[i]=bin[i-1]*11;
    while(scanf("%d%d%d%d%d",&k,&n,&m,&xt,&yt)!=EOF) {
        q.clear();
        sz=bg=0;
        memset(ans,0,sizeof(ans));
        memset(mp,0,sizeof(mp));
        pre();
        xt=(xt+2)%3;
        yt=(yt+2)%3;
        ed=bin[xt*3+yt];
        int x,y,v;
        for(int i=1; i<=k; i++) {
            x=read();
            y=read();
            x=(x+2)%3;
            y=(y+2)%3;
            v=x*3+y;
            bg+=bin[v];
        }
        if(dfs(bg)==1)puts("Yes");
        else puts("No");
    }
    return 0;
}

总结： 得分情况 在 60min + 5min + 0min = 65min 的有效时间内得到了 100 + 20 + 0 = 120分 的成绩。个人认为这套题在与noip题的匹配度上并不大
暴力难度 < noip2018Day1
正解难度本人无法比较，因为实在是实力不允许啊。