水题记录_David1950的博客-程序员秘密

技术标签: 数据结构与算法  

  从noip之后,自己的状态就非常不好。学文化课的时候心里总想着竞赛,真的停课了却又异常浮躁,简单题不想做,难题不会做,错了的题也不改,天天打游戏,静不下心。省选也是各种瞎打,day2T1竟然会因为没有memset掉了40分。虽说苟进了队,但毕竟进的不光彩,若是还以这样的状态下去,潦草离场,那当初选择这条路的意义又在哪里?

  得开始好好学习了啊......

 

4.16

  正式停课的第一天~

  昨天的HNOI考的巨炸,今天就先改改题

  (老吴一大早分析了一波局势,dalao_cxy被寄予厚望,Orz,要向他学习)

  ~~~~~

  只改了Day2两道题 http://www.cnblogs.com/XYZinc/p/8854765.html

  还做了一道@cxy出的dp

  今天效率好低啊

 

4.17

  今天就主要打一些基础算法调整一下状态

  ~~~~~

  • 贪心

  「雅礼集训 2017 Day4」洗衣服

  http://www.cnblogs.com/XYZinc/p/8862632.html

 

  「雅礼国庆 2017 Day5」Repulsed

  很容易想到贪心,对于所有未处理的点,在它的第k祖先处处理必然是最优的
  f[i][j]表示节点i的子树中,距离为j且需要灭火器的点数
  r[i][j]表示从节点i出发,可以向距离不大于j的节点分配的灭火器个数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define ll long long
 5 
 6 inline ll read()
 7 {
 8     ll x = 0, f = 1; char ch = getchar();
 9     while(ch < '0' || ch > '9') {
     if(ch == '-') f = -1; ch = getchar();}
10     while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
11     return x * f;
12 }
13 
14 int n, s, k, ans;
15 vector<int> to[N];
16 
17 ll f[N][25], r[N][25];
18 void dfs(int x, int fa)
19 {
20     f[x][0] = 1;
21     for(int i = 0; i < to[x].size(); i++)
22     {
23         int kk = to[x][i];
24         if(fa == kk) continue;
25         dfs(kk, x);//从叶子节点向上dp
26         for(int j = 1; j <= k; j++)
27             f[x][j] += f[kk][j - 1], r[x][j - 1] += r[kk][j];
28     }
29     if(f[x][k])
30     {
31         int t = f[x][k] / s + (f[x][k] % s != 0);
32         ans += t; r[x][k] += t * s;
33     }
34     int p = k;
35     for(int i = k; i >= 0; i--)//从下到上处理能覆盖的点
36         while(f[x][i])
37         {
38             while(!r[x][p] && p >= i) p--;
39             if(p < i) break;//不能继续处理,退出
40             int t = min(r[x][p], f[x][i]);
41             r[x][p] -= t; f[x][i] -= t;
42         }
43 }
44 
45 int main()
46 {
47     n = read(); s = read(); k = read();
48     for(int i = 1; i < n; i++)
49     {
50         int x = read(), y = read();
51         to[x].push_back(y); to[y].push_back(x);
52     }
53     dfs(1, 0);
54     ll cnt = 0;//最后一起处理距离根k以内的节点
55     for(int i = 0; i <= k; i++) cnt += f[1][i];
56     ans += cnt / s + (cnt % s != 0);
57     cout << ans;
58     return 0;
59 }
View Code

  

  poj1328 Radar Installation

//在x上方给出n个点,要求用最少个数的半径为i,圆心在x轴上的圆覆盖所有点,输出最少需要的圆的个数,无法覆盖输出-1,多组测试数据

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 1005;
const int inf = 2000000000;

int n, ans, T;
int d, x[N], y[N];

struct node
{
    double l, r;
}s[N];

bool cmp(node a, node b)
{
    if(a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}

int main()
{
    while(scanf("%d%d", &n, &d) && n && d)
    {
        T++;
        bool fail = false; ans = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d", &x[i], &y[i]);
            if(y[i] > d) fail = true;
        }
        if(fail) {printf("Case %d: -1\n", T);continue;} 
        //问题转化为在x轴上选出尽量少的点,使所有区间都包含至少一个点}
        for(int i = 1; i <= n; i++)
        {
            double t = sqrt(1.0 * d * d - 1.0 * y[i] * y[i]);
            s[i].l = (double)x[i] - t; s[i].r = (double)x[i] + t;
        }
        sort(s + 1, s + 1 + n, cmp);
        double pos = -inf;//pos记录上一个点的位置
        for(int i = 1; i <= n; i++)
        {
            if(s[i].l > pos)//若两个区间没有交集,点数+1
            {
                ans++;
                pos = s[i].r;
            }
            else if(s[i].r < pos) pos = s[i].r;
        }
        printf("Case %d: %d\n", T, ans);
    }
    return 0;
}
View Code

 

  • 分治

  「LibreOJ β Round #4」游戏

  emmm......读入WA了2次

  难受

  因为X可以填入任意实数,所以填X可以改变逆序对的奇偶,即最后填X的人能直接获胜,判一下X的奇偶即可

  若序列中不存在X,胜负已定,直接计算逆序对个数

  特别地,对于 n = 1 的情况,qmqmqm 必输

#include <bits/stdc++.h>
using namespace std;
#define N 100005

int n,cnt;
int a[N], t[N];

void mergesort(int l, int r)
{
    if(l == r) {t[l] = a[l]; return;}
    int mid = (l + r) >> 1;
    mergesort(l, mid); mergesort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
    {
        if(a[i] > a[j])
        {
            t[k++] = a[j++];
            cnt += (mid - i + 1) % 2;
        }
        else t[k++] = a[i++];
    }
    while(i <= mid) t[k++] = a[i++];
    while(j <= r) t[k++] = a[j++];
    for(int i = l; i <= r; i++) a[i] = t[i];
}

int main()
{
    scanf("%d", &n);
    if(n == 1) {cout << "L"; return 0;}
    for(int i = 1; i <= n; i++)
    {
        char s[15]; scanf("%s", s);
        if(s[0] == 'X') cnt++;
        else
        {
            int x = 0, f = 1, l = strlen(s);
            for(int j = 0; j < l; j++)
            {
                if(s[j] == '-') f = -1;
                else x = x * 10 + s[j] - '0';
            }
            a[++a[0]] = x * f;
        }
    }
    if(!cnt) mergesort(1, a[0]);
    if(cnt % 2) cout << "W"; else cout << "L";
    return 0;
}
View Code

  ~~~~~

  今天效率还是好低啊

 

4.18

   这两天再水一下dp和数据结构,就得开始学习新东西了

  ~~~~~

  luogu1020 导弹拦截

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int a[N], f[N];

int main()
{
    int x; while(scanf("%d", &x) != EOF) {a[++a[0]] = x;}
    for(int i = a[0]; i > 0; i--)
    {
        if(!f[0] || a[i] >= f[f[0]]) f[++f[0]] = a[i];
        else
        {
            int p = upper_bound(f + 1, f + 1 + f[0], a[i]) - f;
            f[p] = a[i];
        }
    }
    printf("%d\n", f[0]); f[0] = 0;
    for(int i = 1; i <= a[0]; i++)
    {
        if(!f[0] || a[i] > f[f[0]]) f[++f[0]] = a[i];
        else
        {
            int p = lower_bound(f + 1, f + 1 + f[0], a[i]) - f;
            f[p] = a[i];
        }
    }
    printf("%d", f[0]);
    return 0;
}
View Code

  

  luogu1880 [NOI1995]石子合并

  mn[i][j]表示合并完区间[i, j]的最小分数

  很容易想到: mn[i][j] = min(mn[i][k] + mn[k + 1][j] + sum(i, j));   (i <= k < j)

  考虑递推顺序,得到mn[i][j]的前提是已经提前算出[i, j]子区间的mn值,枚举 i 或 j 并不是很容易处理

  可以想到枚举区间长度,再用 i 算出 j 值,这样便可以确保所需状态已经求出

  最大值同理

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int inf = 1e9;

int n, a[N], sum[N];
int mn[N][N], mx[N][N];//mn[i][j],mx[i][j]分别代表区间[i,j]合并的最 小/大 得分

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {scanf("%d", &a[i]); a[i + n] = a[i];}
    for(int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i];
    for(int l = 1; l <= n; l++)
        for(int i = 1, j = i + l; j < 2 * n; i++, j++)
        {
            mn[i][j] = inf;
            for(int k = i; k < j; k++)
            {
                mn[i][j] = min(mn[i][j], mn[i][k] + mn[k + 1][j] + sum[j] - sum[i - 1]);
                mx[i][j] = max(mx[i][j], mx[i][k] + mx[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    int ans[2] = {inf, 0};
    for(int i = 1; i <= n; i++)
    {
        ans[0] = min(ans[0], mn[i][i + n - 1]);
        ans[1] = max(ans[1], mx[i][i + n - 1]);
    }
    cout << ans[0] << endl << ans[1];
    return 0;
}
View Code

 

  luogu1140 相似基因

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int inf = 1e9;
const int sim[5][5] = { {
      5, -1, -2, -1, -3},
                        {
       -1, 5, -3, -2, -4},
                        {
       -2, -3, 5, -2, -2},
                        {
       -1, -2, -2, 5, -1},
                        {
       -3, -4, -2, -1, 0} };                        

int n, m, a[N], b[N];
int f[N][N];
char s[N];

void get(int l, int T[N])
{
    for(int i = 0; i < l; i++)
    {
        if(s[i] == 'A') T[i + 1] = 0;
        else if(s[i] == 'C') T[i + 1] = 1;
        else if(s[i] == 'G') T[i + 1] = 2;
        else if(s[i] == 'T') T[i + 1] = 3;
    }
}

int main()
{
    scanf("%d%s", &n, s); get(n, a);
    scanf("%d%s", &m, s); get(m, b);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) f[i][j] = -inf;
    for(int i = 1; i <= n; i++) f[i][0] = f[i - 1][0] + sim[a[i]][4];
    for(int i = 1; i <= m; i++) f[0][i] = f[0][i - 1] + sim[b[i]][4];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i][j], f[i][j - 1] + sim[b[j]][4]);
            f[i][j] = max(f[i][j], f[i - 1][j] + sim[a[i]][4]);
            f[i][j] = max(f[i][j], f[i - 1][j - 1] + sim[a[i]][b[j]]);
        }
            
    cout << f[n][m];
    return 0;
}
View Code

 

  luogu1282 多米诺骨牌

  f[i][j] 表示前 i 个纸牌,上下差值为 j 时的最小翻动次数

  于是就有 f[i][j] = min(f[i - 1][j - (a[i] - b[i])], f[i - 1][j + (a[i] - b[i])])

  注意数组别越界

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

int n, a[N], b[N];
int f[N][15 * N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
    memset(f, 127, sizeof(f)); f[0][0 + 6000] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = -6000; j <= 6000; j++)
        {
            j += 6000;
            f[i][j] = min(f[i - 1][j - a[i] + b[i]], f[i - 1][j - b[i] + a[i]] + 1);
            j -= 6000;
        }
    for(int i = 0; i <= 6000 ; i++)
    {
        int ans = min(f[n][6000 + i], f[n][6000 - i]);
        if(ans <= n) {cout << ans; return 0;}
    }
    return 0;
}
View Code

 

  luogu1508 Likecloud-吃、吃、吃

  从下向上跟从上到下没太大区别

  f[i][j] = max(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]);

  注意宽为奇数,最后答案就是max(f[n][m / 2 ], f[n][m / 2 + 1], f[n][m / 2 + 2]);

#include <bits/stdc++.h>
using namespace std;
const int N = 205;

int n, m;
int mp[N][N], f[N][N];

int main()
{    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) scanf("%d", &mp[i][j]);
    memset(f, -11, sizeof(f));
    for(int i = 0; i <= m + 1; i++) f[0][i] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j + 1]);
            f[i][j] = max(f[i][j], f[i - 1][j]);
            f[i][j] += mp[i][j];
        }
    cout << max(f[n][m / 2], max(f[n][m / 2 + 1], f[n][m / 2 + 2]));
    return 0;
}
View Code

 

  ~~~~~

  今天又被jushen鄙视了

  我该如何委婉地提醒他我比他菜很多这一事实?

 

4.19

  昨天的石子合并复杂度是O(n3),四边形不等式优化一下可以达到O(n2)

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int inf = 1e9;

int n, a[N], sum[N];
int mn[N][N], mx[N][N];//mn[i][j],mx[i][j]分别代表区间[i,j]合并的最 小/大 得分
int sn[N][N];//sn[i][j]代表区间[i,j]合并得到最小值时的k值

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {scanf("%d", &a[i]); a[i + n] = a[i];}
    for(int i = 1; i <= 2 * n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        sn[i][i] = i;
    }
    
    for(int l = 1; l <= n; l++)
        for(int i = 1, j = i + l; j < 2 * n; i++, j++)
        {
            mx[i][j] = max(mx[i][j - 1], mx[i + 1][j]) + sum[j] - sum[i - 1];//最大值不满足单调性,不能用四边形不等式,但最大值总是在端点处取到???
            mn[i][j] = inf;
            for(int k = sn[i][j - 1]; k <= sn[i + 1][j]; k++)
                if(mn[i][j] > mn[i][k] + mn[k + 1][j])
                    {mn[i][j] = mn[i][k] + mn[k + 1][j]; sn[i][j] = k;}
            mn[i][j] += sum[j] - sum[i - 1];
        }
    int ans[2] = {inf, 0};
    for(int i = 1; i < n; i++)
    {
        ans[0] = min(ans[0], mn[i][i + n - 1]);
        ans[1] = max(ans[1], mx[i][i + n - 1]);
    }
    cout << ans[0] << endl << ans[1];
    return 0;
}
View Code

  其实还是有一点不太懂,先挖坑吧,以后会填的

 

  luogu1387 最大正方形

#include <bits/stdc++.h>
using namespace std;
const int N = 105;

int n, m, mp[N][N];
int f[N][N];//f[i][j]表示以(i,j)为右下角的正方形边长

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) scanf("%d", &mp[i][j]);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(!mp[i][j]) f[i][j] = 0;
            else f[i][j] = min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) + 1;
            ans = max(ans, f[i][j]);
        }
    cout << ans;
    return 0;
}
View Code

 

  luogu1417 烹调方案

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
#define ll long long 

int T, n;
ll a[N], b[N], c[N];
ll f[100005];

struct node 
{
    ll a, b, c;
}s[N];

bool cmp(node x, node y)
{
    return x.c * y.b < y.c * x.b;
}

int main()
{
    scanf("%d%d", &T, &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &s[i].a);
    for(int i = 1; i <= n; i++) scanf("%lld", &s[i].b);
    for(int i = 1; i <= n; i++) scanf("%lld", &s[i].c);
    sort(s + 1, s + 1 + n, cmp);
    for(int i = 1; i <= n; i++)//前i件物品
        for(ll j = T; j >= s[i].c; j--)//已经花费的时间
            f[j] = max(f[j], f[j - s[i].c] + s[i].a - j * s[i].b);
    ll ans = 0;
    for(int i = 0; i <= T; i++) ans = max(ans, f[i]);
    cout << ans;
    return 0;
}
View Code

  ~~~~~

  好烦啊,根本看不进去东西

 

4.20

  luogu1736 创意吃鱼法

#include <bits/stdc++.h>
using namespace std;
const int N = 2505;

int n, m, ans;
int l[N][N], r[N][N];
int mp[N][N], f[N][N][2];

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        ans = 0;
        memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                scanf("%d", &mp[i][j]);
                l[i][j] = l[i][j - 1] + mp[i][j];
                r[i][j] = r[i - 1][j] + mp[i][j];
            }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                if(!mp[i][j]) f[i][j][0] = f[i][j][1] = 0;
                else
                {
                    for(int k = f[i - 1][j - 1][0]; k >= 0; k--)//这一层的常数我感觉很小,然而并不会证 
                    {
                        if(r[i][j] - r[i - k - 1][j] != 1) continue;
                        if(l[i][j] - l[i][j - k - 1] != 1) continue;
                        f[i][j][0] = k + 1; break;
                    }
                    for(int k = f[i - 1][j + 1][1]; k >= 0; k--)
                    {
                        if(r[i][j] - r[i - k - 1][j] != 1) continue;
                        if(l[i][j + k] - l[i][j - 1] != 1) continue;
                        f[i][j][1] = k + 1; break;
                    }
                }
                ans = max(ans, max(f[i][j][0], f[i][j][1]));
            }        
        cout << ans << endl;
    }
    return 0;
}
View Code

 

  uoj107【APIO2013】ROBOTS

  

4.24

  又浪了几天......

  难受

  ~~~~~

  bzoj2333: [SCOI2011]棘手的操作

  http://www.cnblogs.com/XYZinc/p/8930911.html

 

4.25

  poj1062 昂贵的聘礼

  dfs

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 105;

int m, n;

struct node
{
    int p, l, sz;
    int t[N], v[N];
}s[N];

bool vis[N];
int dfs(int x, int mn, int mx)
{
    int cnt = s[x].p;
    for(int i = 1; i <= s[x].sz; i++)
    {
        int to = s[x].t[i]; if(vis[to]) continue;
        if(abs(mn - s[to].l) <= m && abs(mx - s[to].l) <= m)
        {
            vis[to] = true;
            cnt = min(cnt, dfs(to, min(mn, s[to].l), max(mx, s[to].l)) + s[x].v[i]);
            vis[to] = false;
        }
    }
    return cnt;
}

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &s[i].p, &s[i].l, &s[i].sz);
        for(int j = 1; j <= s[i].sz; j++) scanf("%d%d", &s[i].t[j], &s[i].v[j]);
    }
    vis[1] = true;
    cout << dfs(1, s[1].l, s[1].l);
    return 0;
}
View Code

 

  poj1797 Heavy Transportation

  kruskal 

  唉,注意输出格式

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1005;
const int M = 1000005;

int T, n, m, fa[N];

struct node{
     int x, y, w;}s[M];

bool cmp(node a, node b) {
     return a.w > b.w;}

int findf(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = findf(fa[x]);
}

void merge(int x, int y)
{
    x = findf(x); y = findf(y);
    if(x != y) fa[x] = y;
}

int main()
{
    scanf("%d", &T);
    for(int id = 1; id <= T; id++)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++) scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].w);
        sort(s + 1, s + 1 + m, cmp);
        for(int i = 1; i <= n; i++) fa[i] = i;
        for(int i = 1; i <= m; i++)
        {
            merge(s[i].x, s[i].y);
            if(findf(1) == findf(n))
            {
                printf("Scenario #%d:\n", id);
                printf("%d\n", s[i].w);
                if (id != T) printf("\n");
                break;
            }
        }
    }
    return 0;
}
View Code

 

4.26

  就水了场比赛

 

4.27

  poj3352 Road Construction

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1005;

char s[30];
int n, m, ans, deg[N];
vector<int> to[N];

int t, dfn[N], low[N]; bool flag[N];
void tarjan(int x, int fa)
{
    dfn[x] = low[x] = ++t; flag[x] = true;
    for(int i = 0; i < to[x].size(); i++)
    {
        int k = to[x][i];
        if(k == fa) continue;
        if(!dfn[k])
        {
            tarjan(k, x);
            low[x] = min(low[x], low[k]);
        }
        else if(flag[k]) low[x] = min(low[x], dfn[k]);
    }
}

void clear()
{
    for(int i = 1; i <= n; i++) to[i].clear();
    memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn));
    memset(flag, 0, sizeof(flag)); memset(deg, 0, sizeof(deg));
    
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        clear();
        for(int i = 1; i <= m; i++)
        {
            int x, y; scanf("%d%d", &x, &y);
            to[x].push_back(y); to[y].push_back(x);
        }
        tarjan(1, 0);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < to[i].size(); j++)
            {
                int k = to[i][j];
                if(low[i] != low[k]) deg[low[i]]++;
            }
        }
        for(int i = 1; i <= n; i++) if(deg[i] == 1) ans++;
        cout << (ans + 1) / 2 << endl;
    }
    return 0;
}
View Code

 

  poj1112 Team Them Up!

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 105;

int n, col[N], sum[3];
int a[N][N], b[N][N], num;
bool mp[N][N], f[N], dp[N][N * 2], id[N][N * 2], fail;

void dfs(int x, int c)
{
    col[x] = c;
    if(c == 1) a[num][++sum[1]] = x;
    else b[num][++sum[2]] = x;
    for(int y = 1; y <= n; y++)
    {
        if(mp[x][y])
        {
            if(col[y])
            {
                if(col[y] != 3 - c) {fail = true; return;}
            }
            else dfs(y, 3 - c);
        }
        if(fail) return;
    }
}

int pos;
vector<int> ans[2];
void print(int i, int dif)
{
    if(!i) return;
    if(!id[i][dif])
    {
        for(int k = 1; k <= a[i][0]; k++) ans[0].push_back(a[i][k]);
        for(int k = 1; k <= b[i][0]; k++) ans[1].push_back(b[i][k]);
        print(i - 1, dif - a[i][0] + b[i][0]);
    }
    else
    {
        for(int k = 1; k <= a[i][0]; k++) ans[1].push_back(a[i][k]);
        for(int k = 1; k <= b[i][0]; k++) ans[0].push_back(b[i][k]);
        print(i - 1, dif + a[i][0] - b[i][0]);
    }
    
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int x; 
        while(scanf("%d", &x) && x) f[x] = 1;
        for(int j = 1; j <= n; j++)
            if(!f[j] && i != j) mp[i][j] = mp[j][i] = true;
        memset(f, 0, sizeof(f));
    }
    for(int i = 1; i <= n; i++)
        if(!col[i])
        {
            sum[1] = sum[2] = 0; num++;
            dfs(i, 1);
            if(fail) {cout << "No solution"; return 0;}
            a[num][0] = sum[1]; b[num][0] = sum[2];
        }
    dp[0][n] = true;
    for(int i = 0; i < num; i++)
    {
        int x = a[i + 1][0] - b[i + 1][0];
        for(int j = -n; j <= n; j++)
            {
                if(!dp[i][j + n]) continue;
                dp[i + 1][j + x + n] = true;
                id[i + 1][j + x + n] = 0;
                dp[i + 1][j - x + n] = true;
                id[i + 1][j - x + n] = 1;
            }
    }
    for(int i = 0; i <= n; i++)
        if(dp[num][n + i]) {pos = i; break;} else if(dp[num][n - i]) {pos = -i; break;}
    print(num, n + pos);
    sort(ans[0].begin(), ans[0].end()); sort(ans[1].begin(), ans[1].end());
    cout << ans[0].size();
    for(int i = 0; i < ans[0].size(); i++) cout << " " << ans[0][i]; cout << endl;
    cout << ans[1].size();
    for(int i = 0; i < ans[1].size(); i++) cout << " " << ans[1][i];
    return 0;
}
View Code

 

4.28

  打了一下fft的板子

  ~~~~~

  被抓去中午给萌新讲动态规划。。。

  我其实很菜的啊。。。

  先预习一波吧。。。

 

4.29

  kd-tree 

 

5.3

   poj3237 Tree

  树链剖分,边权转化为点权

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100005;
const int M = N * 2;
const int inf = 1e9;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {
      if(ch == '-') f  = -1; ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

struct edge
{
    int fr, to, w;
}E[N];

struct node
{
    int l, r, f, mn, mx;
    node(){}
    node(int ll, int rr, int ff, int nn, int xx) {l = ll; r = rr; f = ff; mn = nn; mx = xx;}
}T[N << 3];

int num, to[M], w[M], nt[M], pt[N];
void add(int x, int y, int v) {to[++num] = y; w[num] = v; nt[num] = pt[x]; pt[x] = num;}

int n, sz[N], fa[N], deep[N], son[N];
void dfs1(int x)
{
    sz[x] = 1;
    for(int e = pt[x]; e; e = nt[e])
    {
        int k = to[e];
        if(k == fa[x]) continue;
        fa[k] = x;
        deep[k] = deep[x] + 1;
        dfs1(k);
        sz[x] += sz[k];
        if(sz[k] > sz[son[x]]) son[x] = k;
    }
}

int t, dfn[N], top[N];
void dfs2(int x, int tp)
{
    top[x] = tp; dfn[x] = ++t;
    if(!son[x]) return;
    dfs2(son[x], tp);
    for(int e = pt[x]; e; e = nt[e])
        if(to[e] != son[x] && to[e] != fa[x]) dfs2(to[e], to[e]);
}

void build(int p, int x, int y)
{
    T[p] = node(x, y, 0, inf, -inf);
    if(x == y) return;
    int mid = (x + y) >> 1;
    build(p << 1, x, mid); build(p << 1 | 1, mid + 1, y);
}

void neg(int p)
{
    T[p].mn *= -1; T[p].mx *= -1;
    swap(T[p].mn, T[p].mx);
}

void pushup(int p)
{
    T[p].mn = min(T[p << 1].mn, T[p << 1 | 1].mn);
    T[p].mx = max(T[p << 1].mx, T[p << 1 | 1].mx);
}

void pushdown(int p)
{
    if(T[p].l == T[p].r || !T[p].f) return;
    T[p << 1].f ^= 1; T[p << 1 | 1].f ^= 1;
    neg(p << 1); neg(p << 1 | 1);
    T[p].f = 0;
}

void update(int p, int x, int y, int v)
{
    pushdown(p);
    int pl = T[p].l, pr = T[p].r;
    if(pl == x && pr == y)
    {
        if(v == inf) {T[p].f = 1; neg(p);}
        else T[p].mn = T[p].mx = v;
        return;
    }
    int mid = (pl + pr) >> 1; 
    if(y <= mid) update(p << 1, x, y, v);
    else if(x > mid) update(p << 1 | 1, x, y, v);
    else {update(p << 1, x, mid, v); update(p << 1 | 1, mid + 1, y, v);}
    pushup(p);
}

void Update(int x, int y, int v)
{
    while(top[x] != top[y])
    {
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        update(1, dfn[top[x]], dfn[x], v);
        x = fa[top[x]];
    }
    if(x == y) return;
    if(deep[x] < deep[y]) swap(x, y);
    update(1, dfn[y] + 1, dfn[x], v);
}

int query(int p, int x, int y)
{
    pushdown(p);
    int pl = T[p].l, pr = T[p].r;
    if(pl == x && pr == y) return T[p].mx;
    int mid = (pl + pr) >> 1;
    if(y <= mid) return query(p << 1, x, y);
    else if(x > mid) return query(p << 1 | 1, x, y);
    else return max(query(p << 1, x, mid), query(p << 1 | 1, mid + 1, y));
}

int Query(int x, int y)
{
    int cnt = -inf;
    while(top[x] != top[y])
    {
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        cnt = max(cnt, query(1, dfn[top[x]], dfn[x]));
        x = fa[top[x]];
    }
    if(x == y) return cnt;
    if(deep[x] < deep[y]) swap(x, y);
    cnt = max(cnt, query(1, dfn[y] + 1, dfn[x]));
    return cnt;
}

void clear()
{
    num = t = 0;
    memset(to, 0, sizeof(to)); memset(w, 0, sizeof(w));
    memset(nt, 0, sizeof(nt)); memset(pt, 0, sizeof(pt));
    memset(deep, 0, sizeof(deep)); memset(son, 0, sizeof(son));
    memset(fa, 0, sizeof(fa)); memset(sz, 0, sizeof(sz));
}

int main()
{
    int op = read();
    while(op--)
    {
        clear();
        n = read();
        for(int i = 1; i < n; i++)
        {
            E[i].fr = read(); E[i].to = read(); E[i].w = read();
            add(E[i].fr, E[i].to, E[i].w); add(E[i].to, E[i].fr, E[i].w);
        }
        dfs1(1);
        dfs2(1, 1);
        build(1, 1, t);
        for(int i = 1; i < n; i++)
        {
            if(deep[E[i].fr] > deep[E[i].to]) swap(E[i].fr, E[i].to);
            update(1, dfn[E[i].to], dfn[E[i].to], E[i].w);
        }
        while(true)
        {
            char s[10]; scanf("%s", s);
            if(s[0] == 'C')
            {
                int id = read(), v = read();
                update(1, dfn[E[id].to], dfn[E[id].to], v);
            }
            else if(s[0] == 'N')
            {
                int x = read(), y = read();
                Update(x, y, inf);
            }
            else if(s[0] == 'Q')
            {
                int x = read(), y = read();
                printf("%d\n", Query(x, y));
            }
            else break;
        }
    }
    return 0;
}
View Code

 

5.4

  poj3694 Network

  tarjan

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> 
#include <vector>
using namespace std; 
const int N = 200005;

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;
}

int n, m, cas, Q, ans;
vector<int> to[N];

int t, dfn[N], low[N], fa[N], deep[N]; bool flag[N], br[N];
void tarjan(int x)
{
    dfn[x] = low[x] = ++t; flag[x] = true;
    for(int i = 0; i < to[x].size(); i++)
    {
        int k = to[x][i];
        if(!dfn[k])
        {
            fa[k] = x;
            deep[k] = deep[x] + 1;
            tarjan(k);
            low[x] = min(low[x], low[k]);
            if(dfn[x] < low[k]) ans++, br[k] = true;//br[i]记录i与fa[i]的连边是否为桥
        }
        else if(k != fa[x])low[x] = min(low[x], dfn[k]);
    }
}

void lca(int x, int y)
{
    if(deep[x] < deep[y]) swap(x, y);
    while(deep[x] > deep[y])
    {
        if(br[x]) {ans--; br[x] = false;}
        x = fa[x];
    }
    while(x != y)
    {
        if(br[x]) {ans--; br[x] = false;}
        if(br[y]) {ans--; br[y] = false;}
        x = fa[x]; y = fa[y];
    }
}

void clear()
{
    ans = t = 0;
    for(int i = 1; i <= n; i++) to[i].clear();
    memset(flag, 0, sizeof(flag)); memset(br, 0, sizeof(br));
    memset(deep, 0, sizeof(deep)); memset(fa, 0, sizeof(fa));
    memset(dfn, 0, sizeof(dfn));
}

int main()
{
    n = read(); m = read();
    while(n + m)
    {
        clear();
        printf("Case %d:\n", ++cas);
        for(int i = 1; i <= m; i++)
        {
            int x = read(), y = read();
            to[x].push_back(y); to[y].push_back(x);
        }
        tarjan(1);
        Q = read();
        while(Q--)
        {
            int x = read(), y = read();
            lca(x, y);
            printf("%d\n", ans);
        }
        printf("\n");
        n = read(); m = read();
    }
    return 0;
}
View Code

 

5.5

  又水了一天

 

 

5.10 - 5.14

  丝滑拿铁

  除了意识到自己到底多菜,什么收获也没有

 

5.15

  早上做了一下 NOI2014 DAY1

  接下来的时间打算就这样,早上做题感受一下自己多菜,下午改题,晚上学点新东西

  也不打算学什么太难的东西了,学了也打不出来

  emmm......

  难受

 

5.18 - 5.28

  考试

 

5.28

  两边都没过,没学上了啊

  这段时间真的是完全荒废了,什么都没学,考试的题也没改

  怕是要痛改前非,重新做人啊

 

5.29

  • 分治

  luogu1257

  luogu1429(优美一点的分治,或者旋转坐标轴乱搞)

  • 矩阵快速幂

  luogu1962

  luogu3758

 

6.12

  • 树的直径

  bzoj2282

 

6.13

  • 树的直径

  luogu3761

 

6.15

  bzoj1036 [ZJOI2008]树的统计Count

 

  luogu1072 Hankson 的趣味题

  gcd && lcm

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if(!b) return a;
    return gcd(b, a % b);
}

int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        int a[2], b[2]; scanf("%d%d%d%d", &a[0], &a[1], &b[0], &b[1]);
        int k = a[0] / a[1], t = b[1] / b[0], ans = 0;
        for(int x = 1; x * x <= b[1]; x++)
        {
            if(b[1] % x != 0) continue;
            if(x % a[1] == 0 && gcd(x / a[1], k) == 1 && gcd(t, b[1] / x) == 1) ans++;
            int y = b[1] / x;
            if(x == y) continue;
            if(y % a[1] == 0 && gcd(y / a[1], k) == 1 && gcd(t, b[1] / y) == 1) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}
View Code

 

转载于:https://www.cnblogs.com/XYZinc/p/8795150.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/David1950/article/details/101338258

智能推荐

查看变量内存的python内置函数是_这68个Python内置函数,建议你吃透_weixin_39639653的博客-程序员秘密

内置函数就是Python给你提供的, 拿来直接用的函数,比如print,input等。截止到python版本3.6.2 ,一共提供了68个内置函数,具体如下私信小编【学习】即可获取大量Python学习资料abs() dict() help() min() setattr()all() dir() ...

layer.photos动态加载图片及静态加载图片_Roc.Y的博客-程序员秘密_layer.photos 动画

1.layer组件 - 静态加载图片缩略图//HTML示例&lt;div id="layer-photos-img"&gt; &lt;img src="图片地址"&gt; &lt;img src="图片地址"&gt;&lt;/div&gt; &lt;script&gt; //调用示例 layer.photos({ photos: '#layer-photos-img', anim: 5 //0-6的选择,指定弹出图片动画类型,默认随机(请注...

oracle导出39001,Impdp ORA-39001: invalid argument value ORA-39000: bad dump file specification ORA-316..._weixin_39736547的博客-程序员秘密

HI Oracle Gurus,our Oracle version is 11.2.0.4 RAC.we have a scheduled job, to take expdp backup. then we transfer that backup to linux(production) to windows(FTP site).Today i have transferred dump ...

k8s跨集群网络互通submariner_x10n9的博客-程序员秘密_k8s跨集群访问

至少3个Kubernetes集群,其中一个被指定为中央代理,可供所有连接集群访问;不同的集群需要使用不同的CIDR使用手册:https://submariner.io/operations/usage/假设已有三个集群:集群1的kubeconfig /root/.kube/configip集群2的kubeconfig /root/.kube/configheader集群3的kubeconfig /root/.kube/config3集群1:安装subctlhttps://subma

rs-lidar-16运行cartographer_ros2d建图_m0_38013825的博客-程序员秘密

1.前提:安装好rslidar相关驱动,安装好point_to_laseerscan将点云数据转换成单线激光。2.修改cartographer下的文件,2.1 修改catkin_w/src/cartographer_ros/cartographer_ros/configuration_files/revo_lds.lua,-- Copyright 2016 The Cartograph...

管理器_Chenyaxu的博客-程序员秘密

默认管理器:例 Book.objects.filter(name='朝花夕拾')自定义管理器:books = models.Manager()Book.books.filter(name='朝花夕拾')自定义管理增加额外的方法:class BookManager(models.Manager)        def get_normal_word(self):   ...

随便推点

用 Python 分析《红楼梦》(2)_weixin_33722405的博客-程序员秘密

6 词频统计完成分词以后,词频统计就非常简单了。我们只需要根据分词结果把片段切分开,去掉长度为一的片段(也就是单字),然后数一下每一种片段的个数就可以了。这是出现次数排名前 20 的单词:(括号内为频数)可以跟之前只统计出现次数,不考虑切分问题的排名做个对比:(括号内为频数)通过分词后的词频,我们发现《红楼梦》中的人物戏份由多到少依次是宝玉、...

duri oracle 连接字符串_C#连接Oracle数据库的连接字符串_weixin_39640157的博客-程序员秘密

Oracle XE标准连接Oracle XE(或者"Oracle Database 10g Express Edition")是一个简单免费发布的版本。以下是语法格式:Driver=(Oracle in XEClient);dbq=111.21.31.99:1521/XE;Uid=myUsername;Pwd=myPassword;ODBC新版本连接方式以下是语法格式:Driver={Micros...

【Github万星】50个有趣而又鲜为人知的 Python 特性_机器学习算法与Python学习-公众号的博客-程序员秘密

新智元推荐来源:GitHubPython, 是一个设计优美的解释型高级语言, 它提供了很多能让程序员感到舒适的功能特性。但有的时候, Python 的一些输出结果对于初学者来说似乎...

rman恢复所有数据,控制,参数文件,下_make_zhf的博客-程序员秘密

一rman恢复所有数据,控制,参数文件,下自动恢复spfile文件,自动恢复不了,使用之前备份的文件进行恢复[[email protected] ~]$ rman target  /Recovery Manager: Release 11.2.0.1.0 - Production on Mon Apr 3 01:41:44 2017Copyright (c) 1982

FZU 1759 Super A^B mod C 【欧拉函数 降幂公式】_zhb1nk的博客-程序员秘密

Problem DescriptionGiven A,B,C, You should quickly calculate the result of A^B mod C. (1&lt;=A,C&lt;=1000000000,1&lt;=B&lt;=10^1000000).InputThere are multiply testcases. Each testcase, there is on...

推荐文章

热门文章

相关标签