Day11

【虚】
题意:从数轴的原点开始,有1/4的概率往左或往右走,有1/2的概率被-1s(站在原地不动)。询问t时到p点的概率。
把一个点拆成两个点,则题目可化成有1/2的概率往左或往右走,询问2t时到2p点的概率。可用排列组合求解。
【传送】
题意:一张n*m的图,从(1,1)开始,可以往左或往下走,在一些点有传送门,可以传送到另一个点,询问最大收益。
tarjin缩点+spfa即可。(为什么说的那么简单?因为我还没写出来)。
【串】
题意:n次操作,有p的概率出现1,否则为0。每个长度为x的1可以获得x^3的分数,求答案的期望。
假设在i之前已经出现了x个1,那么如果新加入的是1,对答案的贡献是(x + 1)^3 - x^3, 化简得3x^2 + 3x + 1。
所以,现在只需要维护x^2、x的期望即可。
x的期望:x1[i] = (x1[i - 1] + 1) * x
x^2的期望:x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * x
答案期望:sum += (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * x

7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

接力

【问题描述】

接力共有n名队员(编号1-n)参加,在同一时刻赛道上允许有任意多名选手同时赛跑。比赛开始前,所有交警在起跑线等待起跑。

在t=0时刻,编号为1的选手开始赛跑,L1秒后跑完一圈回到起点。当选手i跑完一圈他会示意Mi名选手开始接力。(选手可能被多次示意,只算最早的示意)每个选手只跑一圈。

接力的总时间为最后一个选手结束赛跑的时间。求接力的总时间。

【输入格式】

第一行一个单独的整数n,表示有n名选手。

接下来n行,每行开始有2个整数Li,Mi,接下来有Mi个整数,表示示意选手的编号。

【输出格式】

一行一个整数,表示接力的总时间。

【输入样例】

5

4 2 2 4

3 3 1 3 4

7 1 5

4 2 3 5

1 0

【输出样例】

14

数据范围与约定

对于30%的数据:n <= 10。

对于60%的数据:n <= 300。

对于100%的数据:n <= 1000。

继续阅读7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

POJ - 3255 Roadblocks

困扰了两天的次短路问题终于在大佬 @C2013ZDX 的帮助下AC了。激动人心😂

传送门:戳我

题目大意:一张无向图,n个点,r条边,求起点1到终点n的次短路。

 

看到题目的时候就懵逼了,最短路好打,可是次短路是什么东东。

后来看了网上的题解,次短路应该是在一段最短路的基础上再加上一段次短路,证明过程不详讲,只要用spfa或dijkstra在记录最短路的时候顺便更新每个点的次短路即可。

 

早上打了个spfa,有时间可以尝试下dijkstra;

由于是无向图所以可以来回走,刚开始没注意到这么gay的条件导致次短路挂掉。。

 

下为code+手打注释

 


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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

const int R=100010;
const int N=5010;

struct dist
{
    int first,second;
    dist()  {
        first = (int)1e9;
        second = (int)1e9;
    }
}dis[N];

int num[2*R],next[2*R],val[2*R],f[N],to[2*R],tot;

queue <int> q;

void adde(int u,int v,int w)    //邻接表
{
    next[++tot]=f[u];
    f[u]=tot;
    to[tot]=v;
    val[tot]=w;
}

void spfa(void)
{
    dis[1].first=0; //1的最短路清零,次短路不能
    q.push(1);
    while (!q.empty())
    {
        int nxt;
        int now=q.front();
        q.pop();
        for (int i=f[now];i;i=next[i])
        {
            int com=dis[now].first+val[i];  //1.起点到now点最短路+到to[i]的距离
            if (com<dis[nxt = to[i]].first)     //更新最短路
            {
                int tem=dis[nxt].first;
                dis[nxt].first=com;
                dis[nxt].second=tem;    //原最短路更新为次短路
                q.push(nxt);
            }
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
            com=dis[now].second+val[i]; //2.起点到now点的次短路加上到to[i]点的距离
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路*2
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
        }
    }
}

int main(void)
{
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
        adde(v,u,w);    //无向图
    }
    spfa();
    printf("%d\n",dis[n].second);
    return 0;
}

 

看到图论就脸黑,还是太过年轻🤣

 

岂曰无衣,与子同袍。

Y.W.             2017/7/11       东海集训

3165糖果

简化下题意就给你k个不等式,让你求出大于0的最小解。

对于不等式a <= b,则a+q <=b+q。所以只要求出一组解,再找到其中的最小值min,用所以解减去min-1即可得出答案


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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<climits>
 
using namespace std;
 
const int N = 100010;
 
struct nod
{
    int a, b, v;
}p[2 * N];
 
struct node
{
    long long v;
    int begin, end;
    node()
    {
        v = INT_MAX;
        begin = INT_MAX;
        end = 0;
    }
}f[N];
 
int n, k, b[N], un_find[N], fuck;
 
bool com(nod a, nod b)
{
    return a.a < b.a;
}
 
void find(int num)
{
    int no;
    if (n == 17 * 5) fuck = -1;
    for (int i = 1;i <= num; i++)
    {
        no = p[i].a;
        f[no].begin = min(f[no].begin, i);
        f[no].end = max(f[no].end, i);
    }
}
 
queue<int> q;
 
int work(int i)
{
    int now = p[i].a, next = p[i].b;
    if (p[i].v == 1)
    {
        if (f[now].v == f[next].v) return 0;
        f[next].v = f[now].v;
        return 1;
    }
    if (p[i].v == 2)
    {
        if (f[now].v < f[next].v) return 0;
        f[next].v = f[now].v + 1;
        return 1;
    }
    if (p[i].v == 5)
    {
        if (f[now].v <= f[next].v) return 0;
        f[next].v = f[now].v;
        return 1;
    }
    return 0;
}
 
void spfa(int t)
{
    b[t] = 1;
    q.push(t);
    while (!q.empty())
    {
        t = q.front();
        un_find[t] = 1;
        for (int i = f[t].begin;i <= f[t].end; i++)
        {
            if (work(i) && !b[p[i].b])
            {
                b[p[i].b] = 1;
                q.push(p[i].b);
            }
        }
        q.pop();
        b[t] = 0;
    }
}
 
void Ans()
{
    long long Min = INT_MAX;
    long long ans = 0;
    for (int i = 1;i <= n; i++)
        Min = min(Min, f[i].v);
    for (int i = 1;i <= n; i++)
        ans += f[i].v - Min + 1;
    cout << ans << endl;
}
 
void change(int i)
{
    int num = p[i].a;
    p[i].a = p[i].b;
    p[i].b = num;
}
 
int main(void)
{
    //freopen("candy.in","r",stdin);
   // freopen("candy.out","w",stdout);
   
    cin >> n >> k;
    int ans = 0, num = k;
    for (int i = 1;i <= k; i++)
    {
       scanf("%d%d%d", &p[i].v, &p[i].a, &p[i].b);
       if ((p[i].v == 2 || p[i].v == 4) && p[i].a == p[i].b)
            ans = -1;
        if (p[i].v == 4)
        {
            change(i);
            p[i].v = 2;
        }
        if (p[i].v == 3)
        {
            change(i);
            p[i].v = 5;
        }
        if (p[i].v == 1)
        {
            p[++num].v = 1;
            p[num].a = p[i].b;
            p[num].b = p[i].a;
        }
    }
    sort(p + 1, p + 1 + num, com);
    find(num);
    if (ans || fuck)
    {
       if (fuck) ans = fuck;
       cout << ans << endl;
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    for (int i = 1;i <= n; i++)
       if (!un_find[i])
           spfa(i);
    Ans();
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}