山西NOIp四校联考部分解题报告

D1T1 Color

题目描述

一个1*n的方格图形 (不可旋转)，用m种颜色填涂每个方格。每个方格只能填涂一种颜色，如果有相邻的方格颜色相同则视为可行方案，问有多少种可行方案。.

输入格式：

两个正整数：m n

输出格式：

一个数：可能的填涂方式总数，mod100003。

输入样例：

2 3

输出样例:

6

样例解释：

6种可能的填涂方式：

0,0,0;   0,0,1;   0,1,1;  1,0,0;   1,1,0;   1,1,1
  • 对于10%的数据：m=2,n<33
  • 对于另外50%的数据：1<m<10000,1<n<=106
  • 对于100%的数据：1<=m<=108,1<=n<=1012

分析

  1. 20分做法：暴力搜索。考场上对于数学题的一般方法。
  2. 其他思路：暴力打表找规律法。
  3. NB方法：排列组合【我不会有木有】。

首先利用暴力搜索打一张表，包含了n = 1..8, m = 1..8的答案。然后开始找规律吧。至于怎么找，那就是仁者见仁智者见智了。我首先设f(n)为n个方格m种颜色的可行方案，g(n)为不可行方案。显然有g(n)=mn−f(n)。然后用某种灵感构造一个数列h(n)=m×h(n−1)+mn−1−h(n−1)。对照表，发现总有f(n)=h(n)−(m−1)n−1。

h(0)=0h(1)=1h(2)=2m−1h(3)=3m2−3m+1h(4)=4m3−6m2+4m−1

发现了半个杨辉三角，根据二项式定理，猜想h(n)=mn−(m−1)2，用归纳法：

h(0)=m0−(m−1)0=0h(n)=m×h(n−1)+mn−1−h(n−1)=[mn−1−(m−1)n−1](m−1)+mn−1=mn−1(m−1+1)−(m−1)n=mn−(m−1)n

原式得证。因此，f(n)=h(n)−(m−1)n−1=mn−(m−1)n−(m−1)n−1。利用快速幂便可以AC。

为什么要描述这种方法呢？注意，考信息不是考数学，计算机不是白给你的。要充分利用计算机暴力快的特点，结合一些奇技淫巧解决问题！代码略。

D1T2 Rigel

题目背景

南欧包括：国家1:罗马尼亚、国家2:保加利亚、国家3:塞尔维亚、国家4:马其顿、国家5:阿尔巴尼亚、国家6:希腊、国家7:斯洛文尼亚、国家8:克罗地亚、国家9:波斯尼亚……。一个名叫Rigel的oier受学校之托乘坐火车通往各个国家处理CCF相关事情。。

题目描述

Rigel决定通过一条铁路线去往各个国家，铁路依此连接国家1，国家2…国家n。该铁路经过n个国家，每个国家都有一个车站。经过两国之间必须购买车票，第k段铁路连接了国家k和国家k+1。为推广本国运输业，每个国家除了发放单次车票Ak。也发放IU卡，使用IU卡的好处是多次往来于该国家可以节约费用，一次乘车费是Bk（Bk<Ak）,但是该卡有工本费Ck.(Iu卡可以无限充值).

Rigel要去m个国家，从城市R1开始分别按照R1,R2,R3…Rm的顺序前往各个国家，可能会多次到达一个国家。相邻访问的国家位置不一定相邻，且不会是同一个国家。

他想知道这一趟处理事务下来，至少会花掉多少的钱，包括购买单次车票、买IU卡和充值的总费用。

输入格式：

第一行两个整数，n，m。
接下来一行，m个数字，表示Ri
接下来n-1行，表示第k段铁路的Ak,Bk,Ck

输出格式：

一个整数，表示最少花费

输入样例：

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10

输出样例：

6394

说明

2-3和8-9为单次车票，其余都是买卡充值。
- 对于30%数据m=2
- 对于另外30%数据 n<=1000,m<=1000
- 对于100%的数据 m,n<=100000,其中Ak,Bk,Ck<=100000

分析

就是luogu月赛的海底高速嘛。由于是离线处理，容易想到用差分数组。一个差分上去，前缀累加，再判断每一段怎么样便宜即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

long long n, m;
long long c[100005];
long long a[100005];
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    memset(c, 0, sizeof c);
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; i++) 
        scanf("%lld", &a[i]);
    for (int i = 1; i < m; i++) {
        long long from = a[i], to = a[i+1];
        if (from > to) swap(from, to);
        c[from]++;
        c[to]--;
    }
    long long sum = 0;
    long long sigma = 0;
    for (int i = 1; i < n; i++) {
        sum += c[i];
        long long ai, bi, ci;
        //printf("%d ", sum);
        scanf("%lld%lld%lld", &ai, &bi, &ci);
        if (ai*sum <= sum*bi+ci) sigma += ai*sum;
        else sigma += sum*bi+ci;
    }
    printf("%lld
", sigma);
    return 0;
}

D2T1 Area

题目描述

小康同学在纸上画了N个平行于坐标轴的矩形，这N个矩形可能有互相覆盖的部分，他想知道这些矩形的总面积是多少。注意，互相覆盖的部分只能算一次。.

输入格式：

输入第一行为一个数N（1≤N≤100），表示矩形的数量。
下面N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–10^8到10^8之间的整数。

输出格式：

输出只有一行，一个整数，表示图形的面积。

输入样例：

3
1 1 4 3
2 -1 3 2
4 0 5 2

输出样例:

10

数据范围

  • 对于40%的数据：n<=40，坐标绝对值<1000
  • 对于100%的数据：n<=100,坐标绝对值<10^8

分析

首先bs这题超纲。。

  1. 40分做法：二维差分数组前缀和累加。毫无脑水。
  2. 100分做法：离散化或漂浮法。漂浮法更好些，于是用漂浮。

漂浮法是计算几何中计算重叠矩形面积的方法。具体来说，就是把矩形放入水中，分为n层，每层一个。从最底端的开始上浮，碰到上面的矩阵就裂开成若干块，直到上浮到顶，就是要求的面积。可以看成你在水面向下俯视，所能看到的就是要浮上来的，也就是总面积。

一个trick：判断矩形相交。

以下内容引用自http://blog.csdn.net/cxf7394373/article/details/7535105

假定矩形是用一对点表达的(minx,miny)(maxx,   maxy)，那么两个矩形rect1{(minx1,miny1)(maxx1,   maxy1)},  rect2{(minx2,miny2)(maxx2,   maxy2)} 相交的结果一定是个矩形，构成这个相交矩形rect{(minx,miny)(maxx, maxy)}的点对坐标是：   
    minx   =   max(minx1,   minx2)   
    miny   =   max(miny1,   miny2)   
    maxx   =   min(maxx1,   maxx2)   
    maxy   =   min(maxy1,   maxy2)   
如果两个矩形不相交，那么计算得到的点对坐标必然满足   
  minx   >   maxx   或者     miny   >   maxy

由于中间有几个步骤没想清楚，分类比较多。代码冗长。。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

struct obj {
        struct point {
                long long x, y;
                point(){}
                point(long long a, long long b) : x(a), y(b) {}
        }; 
        point left_bot, right_top;
        obj() {}
        obj(point a, point b):left_bot(a), right_top(b) {}
        obj(long long a, long long b, long long c, long long d)
        {
                *this = obj(point(a, b), point(c, d));
        }
        operator long long() const 
        {
                return (right_top.x-left_bot.x)*(right_top.y-left_bot.y);
        }
}arr[105];
long long ans = 0;

inline bool fail(long long a, long long b, long long c, long long d)
{
        return a >= c || b >= d;
}

void lift_up(obj rect, int i)
{
        if (i == 0) {
                ans += rect;
                return;
        }
        obj ths = arr[i];
        long long minx = max(ths.left_bot.x, rect.left_bot.x);
        long long miny = max(ths.left_bot.y, rect.left_bot.y);
        long long maxx = min(ths.right_top.x, rect.right_top.x);
        long long maxy = min(ths.right_top.y, rect.right_top.y);
        //printf("%lld %lld %lld %lld
--
", minx, miny, maxx, maxy);
        if (fail(minx, miny, maxx, maxy))
                lift_up(rect, i-1);
        else {
                long long a = rect.left_bot.x, b = rect.left_bot.y, c = rect.right_top.x, d = rect.right_top.y;
                long long e = minx, f = miny, g = maxx, h = maxy;
                if (!fail(a, b, e, d))
                        lift_up(obj(a, b, e, d), i-1);
                if (!fail(e, b, g, f))
                        lift_up(obj(e, b, g, f), i-1);
                if (!fail(e, h, g, d))
                        lift_up(obj(e, h, g, d), i-1);
                if (!fail(g, b, c, d))
                        lift_up(obj(g, b, c, d), i-1);
        }
}

int main()
{
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        ios::sync_with_stdio(false);
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
                long long a, b, c, d;
                cin >> a >> b >> c >> d;
                if (fail(a, b, c, d))
                        arr[i] = obj(0, 0, 0, 0);
                else
                        arr[i] = obj(a, b, c, d);
        }
        for (int i = n; i >= 1; i--)
                lift_up(arr[i], i-1);
        cout << ans << endl;
        return 0;
}

D2T3 review

题目描述

转眼间又到期中考试了，小康同学开始了紧张的复习。教材中总共有N个要复习的知识点，有些知识点之间还存在着单向联系，例如知识点A→B，只要掌握了前置的知识点A，知识点B也能顺利掌握。小康给每个知识点进行了评估，并标出它的相应分值。只要掌握了这个知识点，就获得相应的分数。小康同学现在要选择K个知识点开始复习，使得可以获得最大的分值。

输入描述

第一行：N K (分别表示知识点的个数和选择的知识点)
以下N行，每行两个整数a和b
(a表示这个知识点单向连接的下一个知识点，如果a=0,表示这个知识点没有单向连接的下一个知识点，b表示这个知识点的分值)

输出描述

仅一个数，表示最大得分。

样例输入

8 2
0 1
1 1
2 100
2 100
0 1
5 1
6 2
6 2

样例输出

202

数据范围

  • 对于30%的数据：n<=1000,k<=30
  • 对于60%的数据：n<=50000,k<=100
  • 对于100%的数据：n<=200000,k<=500，1<=b<=1000000

分析

首先说明这个数据弱了：没有环。事实上，题目描述根本没有排除有环的情况，例如：我学了冒泡，可以轻易掌握选择；学了选择，也可以轻易掌握冒泡。这就形成了一个环。所以，标程是有漏洞的！

首先看到数据规模，应该不难想到缩点建图。由于每个点的出度都为0或1，因此，在同一个连通分量中，不会存在两个或以上的环【同《Noip2015 信息传递》】，且任意一个环在缩点后是没有出边的。利用kosaraju缩点建图（比常规要简单一些），不难证明，得到图的转置图必然是森林！。那么必然要选叶子。怎么选呢？贪心！考虑任意两个选择，如果两个选择位于同一个连通分量内，则先后无所谓；如果不是，那先选择结果较大的不可能差于先选结果较小的。因此只需要每次选结果最大的，然后修改其他值【选择这个叶子会把其祖先一起选择，因此会影响到同一连通分量内的其他叶子】，重复选择k次即可。这里用线段树实现。
代码过于坑，考场上一不小心就爆0了。改了一句就AC……

#include <iostream>
#include <cstdio>
#include <cctype>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;

#define maxn (1<<21)
typedef long long ll;
#define lc (k<<1)
#define rc ((k<<1)+1)

struct zkw_heap {
        ll dat[1<<22];
        int from[1<<22];
        zkw_heap()
        {
                memset(dat, 0, sizeof dat);
                for (int i = maxn; i <= maxn+maxn-1; i++)
                        from[i] = i-maxn+1;
        }
        void modify(int i, ll j)
        {
                int p = i+maxn-1;
                dat[p] = j;
                for (int k = p>>1; k; k>>=1) 
                        if (dat[lc] >= dat[rc]) {
                                dat[k] = dat[lc];
                                from[k] = from[lc];
                        } else {
                                dat[k] = dat[rc];
                                from[k] = from[rc];
                        }
               // cout << "--tree " << from[1] << " " << dat[1] << "--
";
        }
}zkw;

ll read() 
{
        ll a = 0;
        int c;
        do c = getchar(); while(!isdigit(c));
        while (isdigit(c)) {
                a = a*10+c-'0';
                c = getchar();
        }
        return a;
}

struct graph {
        struct p {
                int to, next;
        }edge[200005];
        int head[200005], top;
        graph() 
        {
                top = 0;
                memset(head, 0, sizeof head);
        }
        void push(int i, int j)
        {
                edge[++top].to = j;
                edge[top].next = head[i];
                head[i] = top;
        }
} anti, new_anti;

int normal[200005], dealed[200005];
int dfn[200005], top = 0;
int group[200005];
int vis[200005];
int rd[200005], anti_leave[200005];
ll ranks[200005];
ll rk[200005];
int n, gp = 0, k;
void get_dfn(int i)
{
        vis[i] = 1;
        if (!vis[normal[i]] && normal[i] != 0)
                get_dfn(normal[i]);
        dfn[++top] = i;
        //cout << "dfn[" << top << "] = " << i << endl; 
}
void dfs(int i, int gp)
{
        vis[i] = 1;
        group[i] = gp;
        //cout << i << " in group " << gp << endl;
        rk[gp] += ranks[i];
        for (int k = anti.head[i]; k; k = anti.edge[k].next) {
                int to = anti.edge[k].to;
                if (!vis[to] && to != 0)
                        dfs(to, gp);
        }
}

int leaves[200005], num = 0;
long long dp[200005];

long long get_rank(int i)
{
        if (dp[i] != -1) return dp[i];
        if (i == 0) return 0;
        return dp[i] = get_rank(dealed[i]) + rk[i];
}

queue<int> que;
void change(int i)
{
       // cout << "changing " << i << endl;
        vis[i] = 1;
        if (dealed[i] && !vis[dealed[i]])
                change(dealed[i]);
        while (!que.empty()) que.pop();
        que.push(i);
        while (!que.empty()) {
                int k = que.front(); que.pop();
                if (rd[k] == 0) {
                        zkw.modify(anti_leave[k], dp[k] - dp[i]);
                        //dp[k] -= dp[i];
                }
                for (int p = new_anti.head[k]; p; p = new_anti.edge[p].next) 
                        if (!vis[new_anti.edge[p].to])
                                que.push(new_anti.edge[p].to);
        }
}

int main()
{
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        memset(vis, 0, sizeof vis);
        memset(dealed, 0, sizeof dealed);
        memset(anti_leave, 0, sizeof anti_leave);
        memset(dp, -1, sizeof dp);
        memset(rd, 0, sizeof rd);
        n = read(); k = read();
        for (int i = 1; i <= n; i++) {
                normal[i] = read();
                ranks[i] = read();
                if (normal[i])
                        anti.push(normal[i], i);
        }
        for (int i = 1; i <= n; i++)
                if (!vis[i])
                        get_dfn(i);
        memset(vis, 0, sizeof vis);
        for (int i = n; i >= 1; i--)
                if (!vis[dfn[i]])
                        dfs(dfn[i], ++gp);
        for (int i = 1; i <= n; i++)
                if (group[normal[i]] != group[i]) {
                        dealed[group[i]] = group[normal[i]];
                        new_anti.push(group[normal[i]], group[i]);
                        rd[group[normal[i]]]++;
                }
       // for (int i = 1; i <= gp; i++)
       //         cout << rk[i] << " ";
       // puts("");
        // 缩点建图
        for (int i = 1; i <= gp; i++)
                if (rd[i] == 0) {
                        leaves[++num] = i;
                        anti_leave[i] = num;
                        //cout << i << endl;
                }
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= num; i++) {
                zkw.modify(i, get_rank(leaves[i]));
                //cout << leaves[i] << " " << get_rank(leaves[i]) << endl;
        }
        /*for (int i = 1; i <= gp; i++)
                cout << dp[i] << " ";
        puts("");*/
        long long ans = 0;
        for (int i = 1; i <= k; i++) {
                //cout << zkw.from[1] << endl;
                int lvs = leaves[zkw.from[1]];
                //vis[lvs] = 1;
                ans += zkw.dat[1];
               // cout << lvs << " " << zkw.dat[1] << endl;
                int mark = zkw.from[1];
                if (!vis[dealed[lvs]] && dealed[lvs])
                        change(dealed[lvs]);
                zkw.modify(mark, 0);
               /* for (int i = 1; i <= gp; i++)
                        cout << dp[i] << " ";
                puts("");*/
        }
        cout << ans << endl;
        return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ljt12138/p/6684363.html