首页 > 其他分享 >NOIP多校联训18[算数，刷墙，重复，公交]

NOIP多校联训18[算数，刷墙，重复，公交]

时间：2022-11-03 08:11:30浏览次数：51  
标签：fr putchar NOIP int sum Re 联训 刷墙 define

NOIP多校联训18[算数，刷墙，重复，公交]

算数

  • 签到题，考虑所有合法情况只有\(1\)和任意 \(\ge\) 1的数，\(0\) 和任意的正数，负数和任何的正数，就是处理一下一，别算重就行。
  • 复杂度\(O(n)\)
here 
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define Re register int
#define LL long long
#define LD double
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define fr(x, y, z) for(Re x = y; x <= z; x ++)
#define fp(x, y, z) for(Re x = y; x >= z; x --)
#define delfr(x, y, z) for(Re x = y; x < z; x ++)
#define delfp(x, y, z) for(Re x = y; x > z; x --)
#define ki putchar(10)
#define fk putchar(' ')
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define WMX aiaiaiai~~
using namespace std;
namespace kiritokazuto {
	fuc(char, getc)(){
		static char buf[1 << 18], *p1, *p2;
		if(p1 == p2){
			p1 = buf, p2 = buf + fread(buf, 1, 1 << 18, stdin);
			if(p1 == p2)return EOF;
		}
		return *p1++;
	}
	fuc(LL, read)() {
		LL x = 0, f = 1;char c = getc();
		while(!isdigit(c)){if(c == '-')f = -1; c = getc();}
		while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getc();}
		return x * f;
	}
	template <typename T> fuc(void, write)(T x){
		if(x < 0)putchar('-'), x = -x;
		if(x > 9)write(x / 10);putchar(x % 10 | '0');
	}
} 
using namespace kiritokazuto;
const int maxn = 1e6 + 100, Inf = 2147483647, Mod = 1e9 + 7;
int n;
LL a[maxn];
LL cnt = 0;
LL sum[maxn];
LL sum1[maxn];
signed main() {
	#ifdef DEBUG
	frein(in), freout(out);
	#else 
	frein(a), freout(a);
	#endif
	n = read();
	fr(i, 1, n){
		a[i] = read();
		sum[i] = sum[i - 1] + (a[i] > 1);
		sum1[i] = sum1[i - 1] + (a[i] == 1);
	}

	// fr(i, 1, n) {
	// 	fr(j, i + 1, n) {
	// 		if(a[i] * a[j] < a[i] + a[j]) {
	// 			printf("a[%d] = %d a[%d] = %d %d %d\n", i, a[i], j, a[j], a[i] * a[j], a[i] + a[j]);
	// 			cnt++;
	// 		}
	// 	}
	// }
	fr(i, 1, n) {
		if(a[i] == 0) {
			cnt += sum[n] - sum[i] + sum[i - 1];
			cnt += sum1[n];
		}else if(a[i] < 0) {
			cnt += sum[n] - sum[i] + sum[i - 1];
			cnt += sum1[n];
		}else if(a[i] == 1) {
			cnt += sum[n] - sum[i] + sum[i - 1];
			cnt += sum1[n] - sum1[i];
		}
	}
	write(cnt);
	return 0;
}

刷墙

  • 首先这数据范围一看就得离散化，然后就有了\(\le 2 \times n\)个节点，我们设\(dp_{i, j}\)表示\(\color{red}{左右端点都在}\) \([l, r]\)中的区间拼成的答案，因为这个题颜色是在区间里的。
  • 所以我们枚举\([k, k + 1]\)(注意这里两个端点并不是颜色，这个小段是)是什么颜色，将这个颜色最先放，这样两边就变成了\([l, k]\) 和 \([k + 1, r]\)的两个子问题。我们只需要保证存在一个区间经过\([k, k + 1]\)即可，通过二维前缀和(表示左端点\(\le i\)右端点\(\le j\)的区间个数，查询就直接找左端点\(l \le L \le k + 1\)右端点\(k \le R \le r\)就行)统计包含的区间个数然后判断。复杂度\(O(n ^ 3)\)
here 
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define Re register int
#define LL long long
#define LD double
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define fr(x, y, z) for(Re x = y; x <= z; x ++)
#define fp(x, y, z) for(Re x = y; x >= z; x --)
#define delfr(x, y, z) for(Re x = y; x < z; x ++)
#define delfp(x, y, z) for(Re x = y; x > z; x --)
#define ki putchar(10)
#define fk putchar(' ')
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define WMX aiaiaiai~~
using namespace std;
namespace kiritokazuto {
	fuc(char, getc)(){
		static char buf[1 << 18], *p1, *p2;
		if(p1 == p2){
			p1 = buf, p2 = buf + fread(buf, 1, 1 << 18, stdin);
			if(p1 == p2)return EOF;
		}
		return *p1++;
	}
	fuc(LL, read)() {
		LL x = 0, f = 1;char c = getc();
		while(!isdigit(c)){if(c == '-')f = -1; c = getc();}
		while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getc();}
		return x * f;
	}
	template <typename T> fuc(void, write)(T x){
		if(x < 0)putchar('-'), x = -x;
		if(x > 9)write(x / 10);putchar(x % 10 | '0');
	}
} 
using namespace kiritokazuto;
const int maxn = 300 + 100, Inf = 2147483647, Mod = 1e9 + 7;
struct Node {int l, r;}wmx[maxn];
int lsh[maxn << 1], cnt = 0;
int dp[605][605];
int tmp[605];
int n;
int sum[605][605];
fuc(int, get)(int x, int y, int w, int m) {
    return sum[w][m] + sum[x - 1][y - 1] - sum[x - 1][m] - sum[w][y - 1];
}
signed main() {
	#ifdef DEBUG
	frein(in), freout(out);
	#else 
	frein(b), freout(b);
	#endif
    n = read();
    fr(i, 1, n)lsh[++cnt] = wmx[i].l = read(), lsh[++cnt] = wmx[i].r = read();
    sort(lsh + 1, lsh + cnt + 1);
    cnt = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;
    fr(i, 1, n) {
        wmx[i].l = lower_bound(lsh + 1, lsh + cnt + 1, wmx[i].l) - lsh;
        wmx[i].r = lower_bound(lsh + 1, lsh + cnt + 1, wmx[i].r) - lsh;
    }
    fr(i, 1, n)sum[wmx[i].l][wmx[i].r] ++;
    fr(i, 1, cnt)fr(j, 1, cnt)sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    fr(len, 1, cnt) {
        fr(i, 1, cnt) {
            int r = i + len - 1;
            if(r > cnt)break;
            delfr(k, i, r)dp[i][r] = max(dp[i][r], dp[i][k] + dp[k + 1][r] + (get(i, k + 1, k, r) > 0));
        }
    }
    write(dp[1][cnt]);
	return 0;
}

重复

  • 把\(bc\)和\(ef\)合起来记做\(ABDE\)其中\(B = E\), \(A\) 为 \(B\) 的真前缀。枚举每个\(B\)的开头。可以计算出每个\(A\)的开头对\(B\)的哪些长度有贡献。

  • 考虑怎么做，我们先求出一个串内部的\(LCP\)表示一个起点在\(i\)另一个起点在\(j\)能得到的\(LCP\)，考虑处理答案我们先处理出最小的相等的前缀长度，然后第一遍做和求出最大的，第二遍做和就是后缀和\(\ge\)的了。然后就统计就行。

here 
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define Re register int
#define LL long long
#define LD double
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define fr(x, y, z) for(Re x = y; x <= z; x ++)
#define fp(x, y, z) for(Re x = y; x >= z; x --)
#define delfr(x, y, z) for(Re x = y; x < z; x ++)
#define delfp(x, y, z) for(Re x = y; x > z; x --)
#define ki putchar(10)
#define fk putchar(' ')
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define WMX aiaiaiai~~
using namespace std;
namespace kiritokazuto {
	fuc(char, getc)(){
		static char buf[1 << 18], *p1, *p2;
		if(p1 == p2){
			p1 = buf, p2 = buf + fread(buf, 1, 1 << 18, stdin);
			if(p1 == p2)return EOF;
		}
		return *p1++;
	}
	fuc(LL, read)() {
		LL x = 0, f = 1;char c = getc();
		while(!isdigit(c)){if(c == '-')f = -1; c = getc();}
		while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getc();}
		return x * f;
	}
	template <typename T> fuc(void, write)(T x){
		if(x < 0)putchar('-'), x = -x;
		if(x > 9)write(x / 10);putchar(x % 10 | '0');
	}
} 
using namespace kiritokazuto;
const int maxn = 300 + 100, Inf = 2147483647, Mod = 1e9 + 7;


int border[5020][5020];
int sum[5020][5020];
char s[5020];
signed main() {
	#ifdef DEBUG
	frein(in), freout(out);
	#else 
	frein(c), freout(c);
	#endif
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    fp(i, n - 1, 1) {
        fr(j, i + 1, n) {
            if(s[i] == s[j]) {  
                border[i][j] = border[i + 1][j + 1] + 1;
            }else border[i][j] = 0;
        }
    }

    fr(i, 1, n) {
        fr(j, i + 2, n) {
            sum[i][min(j - i - 1, border[i][j])]++;
        }
        fp(j, n, 1)sum[i][j] += sum[i][j + 1];
        fp(j, n, 1)sum[i][j] += sum[i][j + 1];
    }
    LL ans = 0;
    fr(i, 1, n) {
        fr(j, i + 1, n) {
            if(border[i][j] >= j - i) {
                ans += sum[j][j - i + 1];
            }
        }
    }
    write(ans);
    return 0;
}

公交

  • 长剖题..
  • 考虑怎么求一个点的答案，考虑将一个点的点权变为子树的\(size\)和，即选了这个点在线路中答案就会减去$ size\(。那么最终方案一定是每个点选一条向下点权和最大的链（即长链剖分），选择长度前\)k$大
    的加起来。
  • 对于求多个点的答案，注意到挪动一条边，只有\(O(1)\)条链权值会改变，用两个\(set\)第一个维护前\(k\)大，第二个维护剩下的即可，复杂度 \(O(n \log n)\)

标签：fr,putchar,NOIP,int,sum,Re,联训,刷墙,define
From： https://www.cnblogs.com/kiritokazuto/p/16853162.html

相关文章

  • NOIP模拟1
    T1.语言签到题。可以直接\(O(n)\)预处理出来前缀和，但我用了线段树，所以多了一个\(log\)的复杂度。题意转化：找到一个位置为动词，上一个位置为名词，句子末尾是名词，其他地方是......
  • NOIP模拟1
    A.语言想到小学英语老师一遍遍地强调：每个句子有且只有一个动词！！忽然给了我灵感。发现不是动词的部分AN可以自由组合，A可以这样连续A(AN)，A(A(AN))，唯一不合法的情况就是A在末......
  • CSP & NOIP 2022 邮寄
    开坑了。2022/09/18上午在家看了一上午番。下午到CSSYZ门口，发现只有少部分同学已经到了，于是尾随一位女同学去了文具店，买了些笔。重新到校门口，打算去教室放下书包，中途......
  • P1044 [NOIP2003 普及组] 栈 （卡特兰数）
    [NOIP2003普及组]栈题目背景栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（......
  • NOIP 2021 游记
    Day0对着大纲找了点很板子的题做，主要找的dcc和scc缩点、树形DP和DP优化、KMP之类的。睡前祈祷不要失眠，结果在即将睡着后外面传来钢琴声，直接失眠........emmmmmmm。Day1......
  • NOIP 前 CF*2300 左右 dp 做题记录
    iFTL独立做出形象理解为两个横放的羽毛球盒，第一个放长t1的，第二个放长t2的，然后手推可得一次共同发射之后必是平平的盒子底部，仿佛回到了最初，至此可发现子结构。基于此......
  • 洛谷 P1077 [NOIP2012 普及组] 摆花 (DP)
    https://www.luogu.com.cn/problem/P1077题目描述摆上m盆花。一共有n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同......
  • 2022NOIPA层联测16
    数塔：相等上传非常显然，重点是怎么二分(对于这种不知道更大的更优还是更小的更优的题，不知道选哪个二分模板。。)大于等于和小于等于都可以，重要的是取等，就是保证答案在二分......
  • 接水问题（NOIP 2010 PJT2）
      这个的思路就是让各个水龙头所用的时间尽可能地接近，可以先向优先队列中推入前m个数，由于开的是小根堆最小的数在前面我们把它拿出来，加上下一个人所需的时间。如此反复......
  • P2679 [NOIP2015 提高组] 子串
    题意：给定两个串A，B。现在要从字符串 A 中取出 k 个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串。请问有......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99