首页 > 其他分享 >SMU Winter 2024 div2 ptlks的周报Week 3(2.12-2.18)

SMU Winter 2024 div2 ptlks的周报Week 3(2.12-2.18)

时间:2024-02-18 14:00:09浏览次数:40  
标签:Week 100005 Winter int SMU 贡献 2024

这周主要加强了对知识点的掌握。

P10161 [DTCPC 2024] 小方的疑惑 10

从题目可以得知a个连续括号贡献为a(a+1)/2,代价为2a。要求总贡献恰为k,且代价不高于n。
一开始我想到了模拟,先取一个贡献低于k最大的a,剩下的再直接在外面套括号,结果wa。
又想到可以分出多个a来组成k,就用递归,每次取剩余贡献里最大的a,还是wa。
最后发现问题可以类比到dp问题,对每个k进行dp,记录每个最小代价的方案,然后根据所给n,k输出即可

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int a[1005],b[100005];
vector<int> q[100005];

void f(int x,vector<int> t){
	if(x==t.size())return;
	for(int i=0;i<t[x];i++){
		if(i)printf("()");
		else{
			printf("(");
			f(x+1,t);
			printf(")");
		}
	}
}

int32_t main() {
	int T=1;
	cin >> T;
	for(int i=0;i<450;i++){
		a[i]=i*(i+1)/2;
	}
	for (int u = 1; u <=100000; u++){
		int mn=INT64_MAX,mi=1;
		for (int i = 1;  a[i]<=u; i++){
			if(b[u-a[i]]<mn){
				mi=i;
				mn=b[u-a[i]];
			}
		}
		b[u]=mn+mi;
		for(int i=0;i<q[u-a[mi]].size();i++){
			q[u].emplace_back(q[u-a[mi]][i]);
		}
		q[u].emplace_back(mi);
	}

	while (T--) {
		int n,k;
		cin>>n>>k;
		if(b[k]*2>n){
			printf("-1\n");
		}else{
			f(0,q[k]);
			for(int i=0;i<n-b[k]*2;i++){
				printf("(");
			}printf("\n");
		}
	}
}

标签:Week,100005,Winter,int,SMU,贡献,2024
From: https://www.cnblogs.com/ptlks/p/18019188

相关文章

  • winter week3 day1
    2024牛客寒假算法基础集训营2ATokitsukazeandBracelet#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair<string,int>PSI;typedefpair<stri......
  • HGAME 2024 WEEK2 Crypto Misc
    CRYPTOmidRSA题目描述:兔兔梦到自己变成了帕鲁被crumbling抓去打黑工,醒来后连夜偷走了部分flagfromCrypto.Util.numberimport*fromsecretimportflagdefpadding(flag):returnflag+b'\xff'*(64-len(flag))flag=padding(flag)m=bytes_to_long(flag)p=getPrime......
  • 24.02 week 3
    02.14今天是世界上第一台电子计算机ENIAC诞生78周年纪念日,这是一个伟大的日子。没有它,就没有现代社会的一切。昨天看到不少人在热烈讨论,我非常感动,因为竟然有那么多人还记得并庆祝这个伟大的日子。衷心希望电子计算机在下一个78年里蓬勃发展,铸就辉煌。在如此重要的ENIA......
  • ISO8601 week number of the year
      importdatetimedatetime.date(2023,1,1).isoweekday()defleap_year(year:int)->bool:returnyear%4==0andyear%100!=0oryear%400==0foryearinrange(2001,2101):weekday=datetime.date(year,1,1).isoweekday()......
  • [pwn]hgame2024 week1 WriteUp
    目录1.EzSignIn2.ezshellcode3.EldenRandomChallenge1.EzSignIn签到题,直接nc2.ezshellcodechecksec,保护全开64位程序丢IDA跟进一下myread函数可以看到会执行写入的内存,但有两个点一是长度限制,可以通过整型溢出绕过,二是myread函数会检查写入的内容,必须为字母或数字看......
  • winter 2024 第二周周报
    内容winterweek2day1这套题复习了最短路,主要是dp,都是比较好推的dp,还是要多写dp吧,感觉写dp用的时间太久了day2这天是ccf的测试赛,测完就练了套河南大学联赛,10题看当时榜可能第八,只能说队友太给力了。写的那道l感觉挺好想的求方案数,刚开始也是在猜结论,没有想着去好好推qwq,后面......
  • SMU Winter 2024 div2 ptlks的周报Week 2(1.29-2.4)
    这周学习到的知识点有斯特林数(F鸡数题!)F鸡数题!思路第二类斯特林数代码#include<bits/stdc++.h>#defineintlonglong#defineMOD1000000007usingnamespacestd;intn,m,f[100005],fi[100005];intqpow(inta,intn){ intans=1; while(n){ if(n&1){ ......
  • 24.02 week 1 营业日志
    02.01没补完。T1考虑把区间从短到长排列后双指针,那么需要维护一个集合,加区间删区间询问是否有点被覆盖\(m\)次,这个SGT就行了。02.02T1现在不想写。T2这不就是P9981。考虑这个字典序怎么维护,建分层最长路,在每一层中维护所有节点的相对顺序,则比对两个后继只用比对当前......
  • panghu week04 笔记
    长度最小的子数组一开始想的是框定一个区间,然后如果大于等于target,从区间头弹出一个元素,从尾部append进入一个元素,发现并不能覆盖所有的区间看了题解以后,可以定尾,然后移动头部进行比较funcminSubArrayLen(targetint,nums[]int)int{slide:=make([]int,0)slid......
  • winter 2024 第一周周报
    训练内容winter2024day1题解https://www.cnblogs.com/bible-/p/17980600算是考完试后第一场正式训练,练的蓝桥杯,这场不算难打打恢复下状态 winter2024day2题解https://www.cnblogs.com/bible-/p/17983616组队vp了23年新疆那场,6题第三(队友太厉害了qwq),题基本补了。感觉J......