【2017.07.27】基地校集训Day2

题1:牛跑步
题解:搜索。找路径把每个路口看成一个点,找出总条路径,挖掉一个点后如果没有可行路径,此点为必经点。

题2:陈老师搬书
题解:动态规划。难在数组表示什么该怎么用。没什么好说的知道方程怎么列就行。

题3:背单词
题解:弄个快排排每个单词需要用的时间从小到大的顺序,再者就是时间的换算闰年格外注意一下,最后输出在判断一下。

题4:无聊的军官
题解:计算ai到左边第i人需要多少次求出最小公倍数。【应该是这样】

心得体会:连一百都没有【】下次多注意一下坑点吧,然后就是搜索没好好背。

End.

【基地校】2017-7-27 DAY2

By 苏弘烨

NO.1 比大小 compare

【题目】

A君和B君用扑克牌点数比大小 。点数从小到大依次为: 2,3,4,5,6,7,8,9,10,J,Q,K,A。花色不影响点数大小。

比大小的方式:
  1. 共两轮, 每一轮先手玩家先出一张牌, 后手玩家可以根据先手玩家的行动来出一张牌。 打出的牌以后不可再用
  2. 第一轮 A君先手,第二轮由第一轮的胜者先手
  3. 每一轮双方均打出牌后,所出的牌的点数较大的那方即为本轮胜者.若牌点数相等,则本轮先手玩家胜
  4. 每一轮胜者将会得到和其所出的牌点数大小一致的分数
  5.  J、Q、K、A的分数分别视为: 11、12、13、1分。

设 S为最后 A君分数减去B君分数的值, A君目标是最大化 S, n君目标是最小化 S。求S的最终结果。

【MY思路过程】

问题有T组数据,那就for T个循环

先将输入转化为数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
for(int i=1;i<=t;i++)
    {
        int first=1;
        for(int i=1;i<=2;i++)
        {
            char ch;
            cin>>ch;//输入牌点数
            if(ch>='2'&&ch<='9')
            {
                a[i]=ch-'0';
            }
            else
            {
                switch(ch)
                {
                    case 'T': a[i]=10;break;
                    case 'J': a[i]=11;break;
                    case 'Q': a[i]=12;break;
                    case 'K': a[i]=13;break;
                    case 'A': a[i]=15;break;
                }
            }
            cin>>ch;//输入花色,直接省略
        }
        for(int i=1;i<=2;i++)
        {
            char ch;
            cin>>ch;//输入牌点数

            if(ch>='2'&&ch<='9')
            {
                b[i]=ch-'0';
            }
            else
            {
                switch(ch)
                {
                    case 'T': b[i]=10;break;
                    case 'J': b[i]=11;break;
                    case 'Q': b[i]=12;break;
                    case 'K': b[i]=13;break;
                    case 'A': b[i]=15;break;
                }
            }
            cin>>ch;//输入花色,直接省略
 }

 

 

当然,此处应该写成一个函数比较方便。对于“A”,我打算在结算时特别“照顾”。

再开始讨论出什么牌:

我的策略是,先手随机,后手如果2张都比先手大或2张都比先手小,出小的那张;否则出比A大的那张。

最后如果A君比B君大,SA+=点数;else SB+=点数;

(if 点数==15【我预设A为15】 SA/SB+=1)

输出SA-SB即可。

但是这样只过了60%的数据。原因我没有处理好是“A”的分数与点数的关系,如果遇到以下数据就行不通了:

  • A君:3,A
  • B君:4,A

那么,最优方案应该是A,A;3,4。最后S=-3。

但是按照我的策略却变成了A,4;3,A。S=0。不符合最优解。

怎么办呢?我们来看正解。

【正解】

这题是纯模拟题,但是并不简单

花色没有用,所以输入直接省略花色。

我们先编写一个函数,判断点数。


1
2
3
4
5
6
7
8
inline int num(char x) {
  if (x >= '2' && x <= '9') return x - '0';
  if (x == 'T') return 10;
  if (x == 'J') return 11;
  if (x == 'K') return 13;
  if (x == 'Q') return 12;
  return 14;//A的点数
}

再编写一个判断分数的函数


1
2
3
4
5
inline int sco(char x) {
  int y = num(x);
  if (y == 14) y = 1;
  return y;
}

第一轮先手确定打出的牌后, 后手会选择自己两张牌中使得最终结果S较小的那张, 这个 S也就是先手打出的那张牌能得到的分数。

那么,我们就可以再创建一个函数,用来判断。


1
2
3
4
5
6
7
inline int calc(char x, char y, char xx, char yy) {
  if (num(x) >= num(y)) {
    return sco(x) + (num(xx) >= num(yy) ? sco(xx) : -sco(yy));
  } else {
    return -sco(y) + (num(xx) > num(yy) ? sco(xx) : -sco(yy));
  }
}

而先手会在两张牌中取得分较大的那个。

那么,主函数就可以这么写


1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
  scanf("%d", &T);
  while (T--) {
    char a, b, c, d;
    char A, B, C, D;
    scanf(" %c%c %c%c", &a, &A, &b, &B);
    scanf(" %c%c %c%c", &c, &C, &d, &D);

    int ans1 = std::min(calc(a, c, b, d), calc(a, d, b, c));
    int ans2 = std::min(calc(b, c, a, d), calc(b, d, a, c));
    printf("%d\n", std::max(ans1, ans2));
  }
  return 0;
}

完整代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>

int T;

inline int num(char x) {
  if (x >= '2' && x <= '9') return x - '0';
  if (x == 'T') return 10;
  if (x == 'J') return 11;
  if (x == 'K') return 13;
  if (x == 'Q') return 12;
  return 14;
}

inline int sco(char x) {
  int y = num(x);
  if (y == 14) y = 1;
  return y;
}

inline int calc(char x, char y, char xx, char yy) {
  if (num(x) >= num(y)) {
    return sco(x) + (num(xx) >= num(yy) ? sco(xx) : -sco(yy));
  } else {
    return -sco(y) + (num(xx) > num(yy) ? sco(xx) : -sco(yy));
  }
}

int main() {
  scanf("%d", &T);
  while (T--) {
    char a, b, c, d;
    char A, B, C, D;
    scanf(" %c%c %c%c", &a, &A, &b, &B);
    scanf(" %c%c %c%c", &c, &C, &d, &D);

    int ans1 = std::min(calc(a, c, b, d), calc(a, d, b, c));
    int ans2 = std::min(calc(b, c, a, d), calc(b, d, a, c));
    printf("%d\n", std::max(ans1, ans2));
  }
  return 0;
}

NO.2 雷神领域 field

  • 考虑如何快速判断一个点上是否有雷电标记
  • 将图看成一个二分图,对于点(xi,yi),我们将 X中的 xi与 Y中的 yi相连
  • 若一个点的横纵坐标连通, 那么它就是一个雷电标记
  • 并查集实现即可
  • 剩下的问题是个简单的平方 DP
  • F【i】【j】表示走到(i,j)所能遇到的最多的标记数

注:由于对并查集不够了解,此处不细讲,std如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=int(5e3)+1;
int n,a,b,ma,mb,ans,f[MAXN][MAXN],p[MAXN*2];
bool v[MAXN][MAXN];
int Fp(int x) { return (p[x]==x)?x:(p[x]=Fp(p[x])); }
void Union(int x,int y) { if (x!=y) p[y]=x; return ; }

int main() {
  freopen("field.in","r",stdin);
  freopen("field.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=10001;++i) p[i]=i;
    for (int i=1;i<=n;++i) {
        scanf("%d%d",&a,&b);
        ma=max(a,ma); mb=max(b,mb);
        v[a][b]=true; b+=MAXN;
        Union(Fp(a),Fp(b));
    }
    for (int i=1;i<=ma;++i)
        for (int j=1;j<=mb;++j)
            if (!v[i][j]) {
                int pa=Fp(i),pb=Fp(j+MAXN);
                if (pa==pb) v[i][j]=true;
            }
    for (int i=1;i<=ma;++i)
        for (int j=1;j<=mb;++j) {
            f[i][j]=max(f[i-1][j],f[i][j-1])+v[i][j];
            if (f[i][j]>ans) ans=f[i][j];
        }
    printf("%d\n",ans);
    return 0;
}

NO.3朗格拉日计数counter

  • 考虑合法的情况在原序列中的大小关系
  • 共有三种:123,231,312
  • 231 = xx1 − 321 , 312 = 3xx− 321
  • 123,321 用线段树可以方便统计出
  • 而 xx1和3xx也可以方便的求出 (只需要知道后面或后面有多少数比当前大或小)

注:由于线段树是个神马玩意SO std:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cctype>
#include <cstdio>

typedef long long i64;

const int N = 200000 + 10;

int nextInt() {
  char ch;
  while (!isdigit(ch = getchar())) {}
  int res = ch - '0';
  while (isdigit(ch = getchar())) res = 10 * res + ch - '0';
  return res;
}

int n, a[N], b[N];

#define pos(l, r) (((l) + (r)) | ((l) != (r)))

int tag[2 * N];
i64 sum[2 * N];

void build(int l, int r) {
  int id = pos(l, r);
  tag[id] = 0;
  if (l == r) {
    sum[id] = b[l];
    return;
  }
  int mid = (l + r) / 2, lch = pos(l, mid), rch = pos(mid + 1, r);
  build(l, mid);
  build(mid + 1, r);
  sum[id] = sum[lch] + sum[rch];
}

void add(int l, int r, int p, int q) {
  if (p > q) return;
  int id = pos(l, r);
  if (p <= l && r <= q) {
    ++tag[id];
    sum[id] += r - l + 1;
    return;
  }
  int mid = (l + r) / 2, lch = pos(l, mid), rch = pos(mid + 1, r);
  if (tag[id]) {
    tag[lch] += tag[id];
    sum[lch] += tag[id] * (mid - l + 1LL);
    tag[rch] += tag[id];
    sum[rch] += tag[id] * ((i64)r - mid);
    tag[id] = 0;
  }
  if (p <= mid) add(l, mid, p, q);
  if (q > mid) add(mid + 1, r, p, q);
  sum[id] = sum[lch] + sum[rch];
}

void clear(int l, int r, int p) {
  int id = pos(l, r);
  if (l == r) {
    sum[id] = tag[id] = 0;
    return;
  }
  int mid = (l + r) / 2, lch = pos(l, mid), rch = pos(mid + 1, r);
  if (tag[id]) {
    tag[lch] += tag[id];
    sum[lch] += tag[id] * (mid - l + 1LL);
    tag[rch] += tag[id];
    sum[rch] += tag[id] * ((i64)r - mid);
    tag[id] = 0;
  }
  if (p <= mid) clear(l, mid, p); else clear(mid + 1, r, p);
  sum[id] = sum[lch] + sum[rch];
}

i64 query(int l, int r, int p, int q) {
  if (p > q) return 0;
  int id = pos(l, r);
  if (p <= l && r <= q) return sum[id];
  int mid = (l + r) / 2, lch = pos(l, mid), rch = pos(mid + 1, r);
  if (tag[id]) {
    tag[lch] += tag[id];
    sum[lch] += tag[id] * (mid - l + 1LL);
    tag[rch] += tag[id];
    sum[rch] += tag[id] * ((i64)r - mid);
    tag[id] = 0;
  }
  i64 res = 0;
  if (p <= mid) res += query(l, mid, p, q);
  if (q > mid) res += query(mid + 1, r, p, q);
  sum[id] = sum[lch] + sum[rch];
  return res;
}

int main() {
  freopen("counter.in", "r", stdin);
  freopen("counter.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) a[i] = nextInt();
  for (int i = n; i > 0; --i) {
    b[a[i]] = query(1, n, a[i] + 1, n);
    add(1, n, a[i], a[i]);
  }
  build(1, n);
  i64 ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans += query(1, n, a[i] + 1, n);
    add(1, n, 1, a[i] - 1);
    clear(1, n, a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}

东海基地校集训Day2

题1:牛跑步

先求出所有路径,再试着找出挖掉后就到不了终点的点就是必经之路。

题2:陈老师搬书

动态规划。。。

题3:背单词

很直观的题目,主要就是算时间,再从小到大排序,最后再进行判断。

友情提示:时间好好算!

题4:无聊的军官

是时候该动动你聪明的小脑袋了,无能为力。

 

——完。

2017基地校Day2

【T1:牛跑步】(题目

题意:给你一堆路口,告诉你哪几个路口可以相连,找到从1到n号路口的所有路径的必经点;

解法:先找出所有路径,再把每一个点试着挖掉,如果没了这个点就走不到n号路口,那么这就是必经点。要记得,统计有多少个,再按顺序一个一个输出。

【T2:陈老师搬书】(题目

题意,给你三堆书,每本书有自己的重量,每次只能取走任意一堆的最上面的一本书,每次取时有一定的体力系数,第一次体力系数为一,第二次体力系数为二,以此类推;要让每次体力系数乘以书本的重量相加的和最大。

继续阅读2017基地校Day2

【2017.7.27】集训day2

今天又是一个风和日丽的日子,我发现,有std改题就是快,我一下子改了两题,吸取了标程之精华。

题1:就是一个 恶心的题目题不题水不水的,也不知道题目要我求的是什么,幸亏std懂。

题2:雷电领域!就是个二分图加并查集七七八八的加DP,就可以了太水了。

题3:看到题解写的“线段树就可以方便统计出”我就不想改了,题解你倒是跟我说说怎么个线段树啊?std又是个哑巴它也不能解释下为什么。这题就留到后天还是大后天讲了线段树再说吧。

——完

Day12

【质数生成器】
题意:询问区间[m,n]里的质数,1<=m<=n<=10^9,n-m<=1000000。
显然线筛过不了1e9的数据,只能对[m,n]区间求质数。
一个数n如果是合数,那么必定会被sqrt(n)中的质数整除,考虑普通筛(233)。对于[m,n]中的数,只需枚举每个质数,将其在这个区间中的倍数筛去即可。
正确性:线筛只要将sqrt(n)中的质数筛出,大概是1e5左右,明显不会超时。[m,n]区间的普通筛是用质数去筛,比用每个数筛的时间大大减少。
【魔法树】
题意:一棵树,每个点有一种属性。一条路径上的魔法值是这样计算的:在起点的时候,魔法值为 1,每经过一条边,假设这条边拥有的魔法属性是 ci,如果这是奇数次经过带有 ci 魔法属性的边,则将魔法值乘上 ci 对应的魔法系数,否则将魔法值除以 ci 对应的魔法系数。
简化题目,即如果奇数次经过ci的点,那么答案就乘上di,否则这个ci对答案没用贡献。
考虑用二进制来表示每种属性的贡献,对于询问的两个点,只需以任意的点为树根,求出每个点的二进制数,在询问使^即可。
【hill】
题意:给出一座山,求一个最低的点能够看到所有地方。
简单的三分题。

Day1

蒟蒻的我,今天到现在就改了一题,别打我。第三真的。。。。我的贪心插入用得多好,可惜不是正确方法。。。。。

第一题

数学方法,分两种情况,大于N的偶数算,小于N的按奇数算,一大堆特烦的特判。。。

第二题

贪心,每次要爆气球的最优的就是排名大于本身的且需要气球最小的,然后由于气球会减少,可能后边的会超过本身,所以每次计算后有新的比较的人要进入,所以,要用一个优先队列,即可实现每次都是爆最小的且排名大于本身的。

第三题

本题最关键的是当差值越大的数平方越大,所以需要排序,取头尾差平方,可以想到一个一个加入数,然后插入排序,一旦超过就总次数加一,但这样会超时,所以我们要让递增的更快,所以,我们用一个递增,取一个区间,然后对区间进行二分,这样会节省很多时间。

东海集训DAY_1

T1 数学方法,非常easy,但是细节处理忘记一个地方忘记+1;当m/2<n,m>n则 对答案的贡献为(n+1)/2;if(m<n && 3m+1>n)就判断(n-1)/3的奇偶性  特判下即可过;

T2贪心+优先队列 原本早上可以A的结果思路想的过于复杂,贪心想出来但是多做了许多无用的操作 只得了45分;

T3倍增 至今不会改 用贪心骗了40分。