WarYan-CSDN博客

原创 Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final)

Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final)A. Kids Seating题意给你一个数n，让你输出n个数，在1~4n范围内，且他们之间任意两个数都不能直接相除，且gcd不等于1思路因为要使他们gcd不等于1而且任意两个数都不能直接相除，那么要满足这么多数必然是个偶数，在偶数的前提下要使两个数不能直接相除，则倒序输出#include<bits/stdc++.h>using namespace st

2021-01-28 17:40:30 179

原创 Codeforces Round #697 (Div. 3)

Codeforces Round #697 (Div. 3)A. Odd Divisor题意给你一个n(2≤n≤10142\leq n\leq 10^{14}2≤n≤1014)问你n是否有奇数因子不包括1但包括它本身。思路在质因数分解时只有2是偶数，所以不断对一个数除以2，然后判断最后是不是为1就可以。#include<bits/stdc++.h>using namespace std;typedef long long LL;#define int long longcon

2021-01-27 20:09:08 177

原创 Codeforces Round #690 (Div. 3)

Codeforces Round #690 (Div. 3)B. Last Year’s Substring题意让你在字符串中删除一段连续的区间是否能凑齐2020思路如果要删除一段连续的区间那么直接讨论所有情况，因为2020只有4个字符。全在左，全在右…#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;typedef long long LL;void solve() { int n; ci

2021-01-25 18:28:59 207

原创 Codeforces Round #695 (Div. 2)C. Three Bags(思维)

C. Three Bags题意给你三个集合，然后让你将其变为1个，问你最大和。每次操作可以从两个不同的集合中选择a,b然后进行a - b后将a-b放回a所在集合，b丢弃思路参考：https://www.cnblogs.com/JDFZ-ZZ/p/14254933.html每次选择a,b其实就是给a,b建一条边当我们给a,b建一条边后，我们再加入一条边，我们发现整个过程只有深度为奇数的点被减去了(根深度为0)，问题转换为，我们需要找到和最小的奇数点来作为转移。[外链图片转存失败,源站可能有防

2021-01-22 23:01:56 90

原创 Codeforces Round #692 C. Peaceful Rooks

Codeforces Round #692 (Div. 2, based on Technocup 2021 Elimination Round 3)C. Peaceful Rooks题意给你一个n*n的表格和m个(m<n)棋子，棋子不会在同一行或同一列中出现两个，问你最少要多少步才能将其全部移到主对角的位置思路起初想的是我去判断少量的点，来判断他的特殊性，然后我发现(2,3),(3,2)这样的坐标点需要3次，然后如果不是横纵坐标刚好相反的点，但是其所在位置的对角线位置横纵坐标均有棋子存在，

2021-01-22 11:07:28 130

原创 Codeforces Round #696 (Div. 2) D. Cleaning(思维)

题意给你n堆石头，每次你能让相邻的两个石头-1，且开局时你有一个特殊操作可以交换两个相邻的堆。问你能否实现将所有的堆都减为0思路考虑消除过程：给定一个序列:a1,a2,a3,a4...an−2,an−1,ana_1,a_2,a_3,a_4...a_{n-2},a_{n-1},a_na1,a2,a3,a4...an−2,an−1,an正向消除：a1−0,a2−(a1−0),a3−(a2−(a1−0))...a_1-0, a_2-(a_1-0),a_3-(a_2-(a_1-0))..

2021-01-21 18:05:37 168 1

原创 Codeforces Round #685 (Div. 2)B. Non-Substring Subsequence(思维)

B. Non-Substring Subsequence题意给你一个长度为n的01字符串，然后有q次询问，每次询问为l,r，问你有没有不连续的子序列与l,r这段区间内的字符串相等思路刚开始的思路比较奇怪，以为自己猜到了重点，结果vp完以后发现只需要判断第一位和最后一位即可。刚开始我是想如果没有其他解，那么一定是从刚开始连续一直到结尾的这一种解，但是我似乎没有想到l,r区间本身就是这样的。于是我判断了第一位开始是否有r-l位连续的，如果有的话我需要判断下一位的位置是否有多种，如果没有r-l位连续的话

2021-01-20 11:56:21 82

原创 Codeforces Round #688 (Div. 2)C. Triangles(思维+贪心)

题意给你一个n*n的由0~9组成的矩阵，问你相同数组组成的三角形，其中一条边必须平行于x轴或y轴，而且可以自己随机加一个点，然后问你0~9数组分别组成的三角形的面积乘以2的最大值。思路首先找出每个数字的x轴方向最大最小，y轴方向最大最小，然后去遍历每个相应的点和这些最大最小组合后的最大面积。自己选的一个点一定是选在边界的#include<bits/stdc++.h>using namespace std;const int N = 2e3 + 100;typedef long l

2021-01-19 10:34:16 68

原创 Codeforces Round #688 (Div. 2)B. Suffix Operations(思维+贡献)

B. Suffix Operations题意给你n个数，然后有两个规则：给后缀增1给后缀减1其中有一个特殊操作，可以任意修改一个数字。问你使n个数变为相同的最小操作书是多少。思路考虑不加特殊操作的使ai+1a_{i+1}ai+1变为aia_iai的最小代价，ans=abs(ai+1−ai)+abs(ai+2−ai+1)...abs(an−an−1)ans = abs(a_{i + 1} - a_i) + abs(a_{i+ 2}- a{i +1})...abs(a_{n} - a_{

2021-01-19 10:33:46 141

原创 Codeforces Round #689 (Div. 2, based on Zed Code Competition)D. Divide and Summarize(分治+dfs)

D. Divide and Summarize题意给你n个数，q次询问，问你能否具有满足和为s的序列。思路再求其有多少种和时需要使用mid=max+min>>1mid = max + min >> 1mid=max+min>>1来寻找有多少种和。然后dfs，但是需要判断一下左面或者右面全部相等情况，否则会爆栈#include<bits/stdc++.h>using namespace std;const int N = 2e5 + 100;t

2021-01-18 23:19:46 115

原创 Codeforces Round #689 (Div. 2, based on Zed Code Competition)B. Find the Spruce(dp + 重复利用)

B. Find the Spruce题意给你一个n行m列由*或者.组成的图形，一个图形高度为k时当且仅当满足1≤i≤k1 \leq i \leq k1≤i≤k时，第x+i−1x + i - 1x+i−1行必须满足在区间[y−i+1,y+i−1][y - i + 1, y +i-1][y−i+1,y+i−1]全部都是’*’思路暴力解决方法我们暴力判断当前行是否满足，如果满足我们继续将k加大然后继续向下判断，判断k的整个过程具有连续性，比如说当k=3k=3k=3时会重复判断k=2k=2k=2时的情况，

2021-01-18 23:14:26 67

原创 Codeforces Round #689 (Div. 2, based on Zed Code Competition)C. Random Events(思维)

B. Find the Spruce题意给你一个n行m列由*或者.组成的图形，一个图形高度为k时当且仅当满足1≤i≤k1 \leq i \leq k1≤i≤k时，第x+i−1x + i - 1x+i−1行必须满足在区间[y−i+1,y+i−1][y - i + 1, y +i-1][y−i+1,y+i−1]全部都是’*’思路暴力解决方法我们暴力判断当前行是否满足，如果满足我们继续将k加大然后继续向下判断，判断k的整个过程具有连续性，比如说当k=3k=3k=3时会重复判断k=2k=2k=2时的情况，

2021-01-18 21:33:10 86

原创 Educational Codeforces Round 101 (Rated for Div. 2)D. Ceil Divisions

D. Ceil Divisions题意给你n个数，每次可以这样操作(x≢y,ax=⌈ay/ax⌉)(x\not\equiv y,a_x = \lceil{a_y/a_x}\rceil)(x≡y,ax=⌈ay/ax⌉)，问你最多操作n+5次使最后变为一个2和n-1个1思路首先考虑时间复杂度3≤∑n≤2∗1053 \leq \sum n \leq 2*10^53≤∑n≤2∗105我们发现必须在O(nlogn)O(nlogn)O(nlogn)以为来解决这个问题，然后通过找规律我们发现要使其在n

2021-01-18 21:17:42 73

原创 Educational Codeforces Round 101 (Rated for Div. 2)C. Building a Fence(思维+区间处理)

C. Building a Fence题意给你n个基础高度和一个栅栏的长度k，如果建造这整个栅栏的过程可以满足所有规则，那么输出yes规则是：两个连续的相邻栅栏之间必须有长度为1的接触第一个和最后一个栅栏必须和地接触需要注意的是除了第一个和最后一个其他的栅栏也均不能超过地的高度大于k-1思路我们发现我们可以通过处理整个过程的最大高度和最小高度的所处区间来解决问题。设lll为当前的最小高度,rrr为当前的最大高度，当最小高度大于最大高度的时候输出no，然后我们在整个过程中的个

2021-01-18 20:53:36 266

原创 Codeforces Round #693 (Div. 3)G. Moving to the Capital(dfs)

G. Moving to the Capital题意给你n个点m条长度为1的单向边，其中顶点1为中心城市，然后d[i]表示1−>i1->i1−>i的距离。要求：有一次特殊操作可以从d[i]>d[j],i−>jd[i] > d[j], i -> jd[i]>d[j],i−>j，其他的都只能d[i]<d[j],i−>jd[i] < d[j], i ->jd[i]<d[j],i−>j。问你各个顶点在符合要求的条件下移动

2021-01-18 20:28:50 167

原创 Codeforces Round #693 (Div. 3)E. Correct Placement

E. Correct Placement题意你有n个朋友，每个朋友具有hi,wih_i,w_ihi,wi两个属性，让你在满足条件下，求第i个朋友是否具有能放在其前面的朋友，输出对应的id思路因为h,w可以交换，所以我们将所有的h,w中大的作为y，小的作为x，然后按一定的规则排序。排序后我们用双指针去寻找在i前面的最小的朋友，然后将其放到i的前面即可。注意要时刻更新最小值。#include<bits/stdc++.h>using namespace std;const int

2021-01-17 19:34:11 115

原创 Codeforces Round #694 (Div. 2)F. Strange Housing(染色)

题意：给你n个点和m条双向边，让你在满足两个老师不相邻的情况下输出老师的点的集合。思路可以发现是一个染色问题，让你输出染色为某个值的所有点。vis[i]=1vis[i] = 1vis[i]=1表示染成学生,vis[i]=2vis[i] = 2vis[i]=2表示染成老师。假设将u染色为2，则与其相邻的边必须全部染为1如果图不联通输出NO。#include<bits/stdc++.h>using namespace std;const int N = 3e5 + 100;/

2021-01-17 19:23:46 97

原创 Codeforces Round #694 (Div. 2)D. Strange Definition(hash+数学+思维)

D. Strange Definition题目大意：给你nnn个数，qqq次询问。其中xxx和yyy相邻需要满足lcm(x,y)/gcd(x,y)lcm(x,y) / gcd(x,y)lcm(x,y)/gcd(x,y)是一个平方数。每经过1秒，相应的序列会变为和他相邻的集合的乘积。定义did_idi是和aia_iai相邻的元素的个数。让你求最大的did_idi思路：首先化简lcm(x,y)/gcd(x,y)−>x∗y/gcd(x,y)2lcm(x,y)/gcd(x,y)->x

2021-01-17 11:33:52 111

原创 Educational Codeforces Round 102 (Rated for Div. 2)D. Program

D. Program题意给你一个xxx初始值为0，然后给你一系列+−+-+−操作，问你忽略掉[l,r][l, r][l,r]区间的操作后，经过一系列操作，操作过程中会出现多少个不同的数字。比如说:0,1,2算三种,0,1, 0算2种思路容易发现一个区间[x,y][x,y][x,y]其中出现的数的可能有max([x,y])−min([x,y])max([x,y])-min([x,y])max([x,y])−min([x,y])但是需要注意和0的关系问题，因为xxx的初始值为0。三种情况分情况讨论：

2021-01-16 22:24:48 106

原创浙大版《Python 程序设计》题目集第6章函数-6 缩写词

第6章函数-6 缩写词def acronym(phrase): res = "" lst = phrase.split() for i in lst: res += i[0].upper() return res

2021-01-15 01:07:08 374

原创浙大版《Python 程序设计》题目集第6章函数-5 使用函数求余弦函数的近似值

第6章函数-5 使用函数求余弦函数的近似值import mathdef fac(n): res = 1 for i in range(1, n + 1): res *= i return resdef funcos(eps, x): res = 0 flag = 1 cnt = 0 while True: q = flag * math.pow(x, cnt) / fac(cnt) if ab

2021-01-15 01:06:38 480

原创浙大版《Python 程序设计》题目集第6章函数-4 使用函数输出指定范围内Fibonacci数的个数

第6章函数-4 使用函数输出指定范围内Fibonacci数的个数def fib(n): if n == 0: return 1 if n == 1: return 1 a, b = 1, 1 for i in range(2, n + 1): a, b = b, a + b return bdef PrintFN(m,n): lst = [] for i in range(0, 27):

2021-01-15 01:06:07 506 1

原创浙大版《Python 程序设计》题目集第6章函数-3 使用函数统计指定数字的个数

第6章函数-3 使用函数统计指定数字的个数def CountDigit(number, digit): res = 0 number = abs(number) while(number): t = number % 10 if t == digit: res += 1 number /= 10 number = int(number) return res...

2021-01-15 01:05:36 358

原创浙大版《Python 程序设计》题目集第6章函数-2 使用函数求素数和

第6章函数-2 使用函数求素数和import mathdef prime(p): if p == 1: return False for i in range(2, int(math.sqrt(p) + 1)): if p % i == 0: return False return Truedef PrimeSum(m,n): res = 0 for i in range(m, n + 1):

2021-01-15 01:05:05 351

原创浙大版《Python 程序设计》题目集第6章函数-1 使用函数求特殊a串数列和

第6章函数-1 使用函数求特殊a串数列和def fn(a, n): res = 0 for i in range(1, n + 1): t = 0 for j in range(i): t = t * 10 + a res += t return resdef fn(a, n): res = 0 t = 0 for i in range(1, n + 1): t =

2021-01-15 01:04:40 1033

原创浙大版《Python 程序设计》题目集第7章-1 词频统计

第7章-1 词频统计import syss = sys.stdin.read()#系统标准输入模块一次读入s = s[:s.find("#")]#通过find函数来截断t = set([i if not i.isalnum() and i != '_' else " " for i in s])#将不符合条件的都变为空格for i in t: s = s.replace(i, " ")#进行替换不符合的为空格word = s.lower().split(" ")dic = {}for

2021-01-15 01:03:53 532 1

原创浙大版《Python 程序设计》题目集第6章-8 输出全排列

第6章-8 输出全排列import randomn = int(input())t = []tot = 1for i in range(1, n + 1): tot = tot * i t.append(str(i))s = set()while len(s) < tot:#时间复杂度是7!完全可以这样做 random.shuffle(t)#随机生成序列 s.add(''.join(t))#set中去重 #print('debug : ')

2021-01-14 18:44:08 133

原创浙大版《Python 程序设计》题目集第6章-7 找出总分最高的学生

第6章-7 找出总分最高的学生n = int(input())ans = []for i in range(0, n): t = list(map(str, input().split())) Student = dict() Student['id'] = t[0] Student['name'] = t[1] Student['s1'] = int(t[2]) Student['s2'] = int(t[3]) Student['s3'] =

2021-01-14 18:43:37 795

原创浙大版《Python 程序设计》题目集第6章-6 求指定层的元素个数

第6章-6 求指定层的元素个数str1 = input()k = int(input())str2 = str1.replace('[', '').replace(']', '')lst = str2.split(',')lst = [int(t) for t in lst]res = 0n = 0for i in range(len(str1)): if str1[i] == '[': n += 1 elif str1[i] == ']':

2021-01-14 18:43:03 87

原创浙大版《Python 程序设计》题目集第6章-5 列表元素个数的加权和(1)

第6章-5 列表元素个数的加权和(1)str1 = input()str2 = str1.replace('[', '').replace(']', '')lst = str2.split(',')lst = [int(t) for t in lst]res = 0n = 0for i in range(len(str1)): if str1[i] == '[': n += 1 elif str1[i] == ']': n -= 1 el

2021-01-14 18:42:36 205

原创浙大版《Python 程序设计》题目集第6章-4 列表数字元素加权和(1)

第6章-4 列表数字元素加权和(1)str1 = input()str2 = str1.replace('[', '').replace(']', '')lst = str2.split(',')lst = [int(t) for t in lst]res = 0n = 0cnt = 0for i in range(len(str1)): if str1[i] == '[': n += 1 elif str1[i] == ']': n -= 1

2021-01-14 18:41:36 379

原创浙大版《Python 程序设计》题目集第6章-3 列表或元组的数字元素求和

第6章-3 列表或元组的数字元素求和str1 = input().replace('(', '').replace(')', '').replace('[', '').replace(']', '').split(',')tot = 0for i in str1: if '"' not in i: tot += int(i)print(tot)

2021-01-14 18:41:09 282 1

原创浙大版《Python 程序设计》题目集第6章-2 一帮一

第6章-2 一帮一n = int(input())lst1 = []lst2 = []lst3 = []for i in range(n): t = input().split() lst3.append(t[1]) if t[0] == '0': lst1.append(t[1]) else: lst2.append(t[1])for i in range(int(n / 2)): if lst3[i] in lst1:

2021-01-14 18:40:35 161

原创浙大版《Python 程序设计》题目集第6章-1 输入列表，求列表元素和(eval输入应用）

第6章-1 输入列表，求列表元素和(eval输入应用）lst = list(eval(input()))print(sum(lst))

2021-01-14 18:39:38 395

原创浙大版《Python 程序设计》题目集第5章-11 字典合并

第5章-11 字典合并a = dict(eval(input()))b = dict(eval(input()))for i in b.keys(): a[i] = a.get(i, 0) + b[i]t = list(a.items())t.sort(key=lambda x: ord(x[0]) if type(x[0]) == str else x[0])c = str(dict(t)).replace(' ', '').replace("'", '"')print(c).

2021-01-14 18:39:10 262

原创浙大版《Python 程序设计》题目集第5章-10 两数之和

第5章-10 两数之和lst = list(map(int, input().split(',')))n = int(input())d = {}for i in lst: d[i] = n - ifor key, val in d.items(): if key in lst and val in lst: print(lst.index(key), lst.index(val)) breakelse: print('no answer'

2021-01-14 18:38:00 97

原创浙大版《Python 程序设计》题目集第5章-9 求矩阵鞍点的个数

第5章-9 求矩阵鞍点的个数n = int(input())a = []for i in range(n): s = input() a.append([int(t) for t in s.split()])res = 0for j in range(n): for k in range(n): cnt = 0 for k1 in range(n): if a[j][k] >= a[j][k1]:

2021-01-13 10:18:52 193

原创浙大版《Python 程序设计》题目集第5章-8 能被3,5和7整除的数的个数（用集合实现）

第5章-8 能被3,5和7整除的数的个数（用集合实现）m, n = input().split()m, n = int(m), int(n)set3 = set()set5 = set()set7 = set()res = set()for i in range(m, n + 1): if i % 3 == 0: set3.add(i) if i % 5 == 0: set5.add(i) if i % 7 == 0: s

2021-01-13 10:18:22 680

原创浙大版《Python 程序设计》题目集第5章-7 列表去重

第5章-7 列表去重lst = eval(input())lst1 = list(set(lst))lst1.sort(key=lst.index)print(*lst1)

2021-01-13 10:17:51 182

原创浙大版《Python 程序设计》题目集第5章-6 统计工龄

第5章-6 统计工龄n = int(input())lst = list(map(int, input().split()))d = {}for i in range(0, n): if not lst[i] in d: d[lst[i]] = 1 else: d[lst[i]] += 1for j in sorted(d.keys()): print(j, end=':') print(d[j])

2021-01-13 10:17:21 301

c语言课设：火车订票系统

空空如也