ARC063

C - 一次元リバーシ / 1D Reversi

不同的颜色段数-1

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

char s[MAXN];

void Solve() {

    scanf("%s",s + 1);

    N = strlen(s + 1);

    int cnt = 0;

    for(int i = 2 ; i <= N ; ++i) {

	if(s[i] != s[i - 1]) ++cnt;

    }

    out(cnt);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

D - 高橋君と見えざる手 / An Invisible Hand

利润最大是从某个位置之后的最大值减去该位置的值，因为a两两不同，所以假如从位置x买入，从某个y全部卖出可以得到最大利润，那么y最多只有一个

统计有几个x会有这样的y，然后这就是我们需要至少降低一个的位置

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,T;

int a[MAXN];

set<int> S;

void Solve() {

    read(N);read(T);

    for(int i = 1 ; i <= N ; ++i) read(a[i]);

    int D = 0;

    for(int i = N ; i >= 1 ; --i) {

	if(S.size()) {

	    auto t = *(--S.end());

	    D = max(t - a[i],D);

	}

	S.insert(a[i]);

    }

    S.clear();

    int ans = 0;

    for(int i = N ; i >= 1 ; --i) {

	if(S.size()) {

	    if(S.find(a[i] + D) != S.end()) ++ans;

	}

	S.insert(a[i]);

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

E - 木と整数 / Integers on a Tree

我们把一个固定数值的点作为根，然后默认每次走一条边都+1

我们遇到已经固定值的点，可能需要把一些边从+1改成-1，所以算出来的值必须和固定值得差值是偶数

我们算出每个固定数值的点上面需要有多少改成-1的边，记录一个子树最大值

重新从根遍历整棵树，如果子树中最大值仍然大于1，就把连向这个儿子的边改为-1，遍历到一个点时看看当前是否合法，不合法就是-1

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next;

}E[MAXN * 2];

int N,head[MAXN],sumE,K,val[MAXN],c[MAXN],dp[MAXN],mv[MAXN];

bool vis[MAXN];

bool flag = 0;

void add(int u,int v) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    head[u] = sumE;

}

void dfs(int u,int fa) {

    mv[u] = 1e9;

    if(vis[u]) {

	if(val[u] > c[u] || ((c[u] - val[u]) & 1)) {flag = 1;}

	else dp[u] = (c[u] - val[u]) / 2;

	mv[u] = dp[u];

    }

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa) {

	    c[v] = c[u] + 1;

	    dfs(v,u);

	    mv[u] = min(mv[u],mv[v]);

	}

    }

}

bool dfs2(int u,int fa,int d) {

    c[u] -= d * 2;

    if(vis[u] && c[u] != val[u]) return false;

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa) {

	    int t = d;

	    if(mv[v] - d > 0) ++t;

	    if(!dfs2(v,u,t)) return false;

	}

    }

    return true;

}

void Solve() {

    read(N);

    int a,b;

    for(int i = 1 ; i < N ; ++i) {

	read(a);read(b);

	add(a,b);add(b,a);

    }

    read(K);

    int v,p;

    for(int i = 1 ; i <= K ; ++i) {

	read(v);read(p);

	vis[v] = 1;val[v] = p;

    }

    int rt;

    for(int i = 1 ; i <= N ; ++i) {

	if(vis[i]) {rt = i;break;}

    }

    c[rt] = val[rt];

    dfs(rt,0);

    if(flag) {puts("No");return;}

    if(!dfs2(rt,0,0)) {puts("No");return;}

    puts("Yes");

    for(int i = 1 ; i <= N ; ++i) {out(c[i]);enter;}

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

F - すぬけ君の塗り絵 2 / Snuke's Coloring 2

这个需要注意到一个性质，答案的下界是\(2max(H,W) + 1\)

这告诉我们什么，这个空白矩形最优答案一定过\(y = H / 2\)或\(x = W / 2\)

我们就可以对x进行排序，从前往后遍历，存两个单调栈，一个栈底到栈顶递增，y值都小于H/2，一个栈底到栈顶递减，y值都大于H / 2

对于一个i，我们要存的是当前栈里在i+1及以后最大的\(y_1\)小于H / 2，\(y_2\)大于H/2，存一个\(y_2 - y_1\)

我们要找的就是\((y _2 - y_1) - x_{i}\)最大的那个i，然后加上当前遍历到的\(x\)，就是以x为右边界可能被计入答案的最大的矩形

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 300005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int l,r,ad,v;

}tr[MAXN * 4];

int W,H,N,ans;

pii p[MAXN];

int sta[2][MAXN],top[2];

void update(int u) {

    tr[u].v = max(tr[u << 1].v,tr[u << 1 | 1].v);

}

void addlz(int u,int v) {

    tr[u].ad += v;tr[u].v += v;

}

void pushdown(int u) {

    if(tr[u].ad) {

        addlz(u << 1,tr[u].ad);

        addlz(u << 1 | 1,tr[u].ad);

        tr[u].ad = 0;

    }

}

void build(int u,int l,int r) {

    tr[u].l = l;tr[u].r = r;tr[u].ad = 0;

    if(l == r) {

        tr[u].v =  H - p[l].fi;return;

    }

    int mid = (l + r) >> 1;

    build(u << 1,l,mid);

    build(u << 1 | 1,mid + 1,r);

    update(u);

}

void add(int u,int l,int r,int v) {

    if(l > r || !v) return;

    if(tr[u].l == l && tr[u].r == r) {

        addlz(u,v);return;

    }

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) >> 1;

    if(r <= mid) add(u << 1,l,r,v);

    else if(l > mid) add(u << 1 | 1,l,r,v);

    else {add(u << 1,l,mid,v);add(u << 1 | 1,mid + 1,r,v);}

    update(u);

}

int query(int u,int l,int r) {

    if(l > r) return 0;

    if(tr[u].l == l && tr[u].r == r) return tr[u].v;

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) >> 1;

    if(r <= mid) return query(u << 1,l,r);

    else if(l > mid) return query(u << 1 | 1,l,r);

    else return max(query(u << 1,l,mid),query(u << 1 | 1,mid + 1,r));

}

int Calc() {

    sort(p + 1,p + N + 1);

    build(1,0,N);

    top[0] = top[1] = 0;

    memset(sta,0,sizeof(sta));

    int res = 0;

    for(int i = 1 ; i <= N ; ++i) {

        res = max(res,query(1,0,i - 1) + p[i].fi);

        if(p[i].se > H / 2) {

            int pre = H,pos = i;

            while(top[1] && p[sta[1][top[1]]].se > p[i].se) {

                add(1,sta[1][top[1]],pos - 1,-pre);

                pre = p[sta[1][top[1]]].se;

                pos = sta[1][top[1]];

                --top[1];

            }

            add(1,sta[1][top[1]],pos - 1,-pre);

            add(1,sta[1][top[1]],i - 1,p[i].se);

            sta[1][++top[1]] = i;

        }

        else {

            int pre = 0,pos = i;

            while(top[0] && p[sta[0][top[0]]].se < p[i].se) {

                add(1,sta[0][top[0]],pos - 1,pre);

                pre = p[sta[0][top[0]]].se;

                pos = sta[0][top[0]];

                --top[0];

            }

            add(1,sta[0][top[0]],pos - 1,pre);

            add(1,sta[0][top[0]],i - 1,-p[i].se);

            sta[0][++top[0]] = i;

        }

    }

    res = max(res,query(1,0,N) + W);

    return 2 * res;

}

void Solve() {

    read(W);read(H);read(N);

    for(int i = 1 ; i <= N ; ++i) {

        read(p[i].fi);read(p[i].se);

    }

    ans = 2 * max(H,W) + 1;

    ans = max(ans,Calc());

    for(int i = 1 ; i <= N ; ++i) swap(p[i].fi,p[i].se);

    swap(W,H);

    ans = max(ans,Calc());

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

最新文章

  1. Owin SelfHost Asp.net WebApi 遇到 No type was found that matches the controller named &#39;ControllerName&#39; 异常的解决方案
  2. 推荐20款基于 jQuery &amp; CSS 的文本效果插件
  3. linux tar命令简介
  4. host，nslookup,dig 命令安装
  5. spring log4j.properties 没有日志的问题
  6. oracle中DDL DML指什么？
  7. web.xml的深入学习
  8. .NET开发之窗体间的传值转化操作
  9. QRadioButton类中Toggled()信号的使用方法
  10. 需要保存数据zabbix，不需要保存数据nagios
  11. 【Xamarin挖墙脚系列：使用Xamarin进行Hybrid应用开发】
  12. Redis应用场景 及其数据对象 string hash list set sortedset
  13. Facebook登录 AndroidStudio
  14. HeadFirst设计模式 之 C++实现(二)：Observer(观察者模式)
  15. apt-get 依赖修复
  16. 呵呵哒，LNMP下通过fread方式下载文件时，中文名称文件找不到文件
  17. python_如何在一个for循环中迭代多个可迭代对象?
  18. RESTClient
  19. 数据的偏度和峰度——df.skew()、df.kurt()
  20. vue中$emit 和$on 和$set的用法

热门文章

  1. DE2-115 以太网通信之一88E1111网卡接收PC数据
  2. 使用scp上传ssh公钥到服务器
  3. nodejs基础 用http模块 搭建一个简单的web服务器 响应纯文本
  4. luogu2331
  5. Selenium高亮显示定位到的元素
  6. getFieldDecorator用法（二）——封装表单模块
  7. arcgis python xlstoshp
  8. 自定义Camera的setPictureSize拍照完毕出现花屏怎么解决
  9. 阶段5 3.微服务项目【学成在线】_day05 消息中间件RabbitMQ_16.RabbitMQ研究-与springboot整合-生产者代码
  10. JAVA 基础编程练习题48 【程序 48 加密】