Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


qbxt Day1 解题报告

上午==>

T1 立方数

题目描述

LYK定义了一个数叫“立方数”,若一个数可以被写作是一个正整数的3次方,则这个数就是立方数,例如1,8,27就是最小的3个立方数。
现在给定一个数P,LYK想要知道这个数是不是立方数。
当然你有可能随机输出一些莫名其妙的东西来骗分,因此LYK有T次询问~


输入格式

第一行一个数T,表示有T组数据。
接下来T行,每行一个数P。


输出格式

输出T行,对于每个数如果是立方数,输出“YES”,否则输出“NO”。

输入样例

3
8
27
28


输出样例

YES
YES
NO


数据范围

对于30%的数据p<=100。
对于60%的数据p<=10^6。
对于100%的数据p<=10^18,T<=100。

emmmmmm

真是超级水。暴力判断竟然A了……当时打暴力时为了降复杂度,在一个if中同时判断x[i],x[n2+i],x[n3+i]······相当于把一段区间分成好几段,同时在这好几段中判断,这样复杂度就可以降一些···emmm对打暴力还是挺有用的(我认为)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#define n 100000
#define LL long long
#define ULL unsigned long long
using namespace std;
int T;
ULL x[1000005];
ULL read(){
ULL sum = 0,fg=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-') fg = -1;
c = getchar();
}
while(c>='0'&&c<='9'){
sum = sum*10+c-'0';
c = getchar();
}
return sum;
}
bool check(ULL p){
for(int i = 1;i <= n;i++)
if(x[i]==p||x[n*2+i]==p||x[n*3+i]==p||x[n*4+i]==p||x[n*5+i]==p||x[n*6+i]==p||x[n*7+i]==p||x[n*8+i]==p||x[n*9+i]==p)
return true;
return false;
}
int main(){
freopen("cubic.in","r",stdin);
freopen("cubic.out","w",stdout);
for(int i = 1;i <= 1000002;i++) x[i] = (ULL)i*i*i;
scanf("%d",&T);
while(T--){
ULL a;
a = read();
if(check(a)) printf("YES\n");
else printf("NO\n");
}
return 0;
}


T2 立方数2

题目描述

LYK定义了一个数叫“立方数”,若一个数可以被写作是一个正整数的3次方,则这个数就是立方数,例如1,8,27就是最小的3个立方数。
LYK还定义了一个数叫“立方差数”,若一个数可以被写作是两个立方数的差,则这个数就是“立方差数”,例如7(8-1),26(27-1),19(27-8)都是立方差数。
现在给定一个数P,LYK想要知道这个数是不是立方差数。
当然你有可能随机输出一些莫名其妙的东西,因此LYK有T次询问~
这个问题可能太难了…… 因此LYK规定P是个质数!


输入格式(cubicp.in)

第一行一个数T,表示有T组数据。
接下来T行,每行一个数P。


输出格式(cubicp.out)

输出T行,对于每个数如果是立方差数,输出“YES”,否则输出“NO”。


输入样例

5
2
3
5
7
11


输出样例

NO
NO
NO
YES
NO


数据范围

对于30%的数据p<=100。
对于60%的数据p<=10^6。
对于100%的数据p<=10^12,T<=100。

emmmmmmmmmmm

看到立方差就应该能想到立方差公式吧:a^3-b^3 = (a-b)(a^2 + ab + b^2),因为p为质数,所以a-b = 1,把a用b+1替换,所以整个式子就可以变成bb3+b*3+1,把第一问的代码稍微改改就水过去了······

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#define n 100000
#define LL long long
#define ULL unsigned long long
using namespace std;
int T;
ULL x[1000005];
ULL read(){
ULL sum = 0,fg=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-') fg = -1;
c = getchar();
}
while(c>='0'&&c<='9'){
sum = sum*10+c-'0';
c = getchar();
}
return sum;
}
bool check(ULL p){
for(int i = 1;i <= n;i++)
if(x[i]==p||x[n*2+i]==p||x[n*3+i]==p||x[n*4+i]==p||x[n*5+i]==p||x[n*6+i]==p||x[n*7+i]==p||x[n*8+i]==p||x[n*9+i]==p)
return true;
return false;
}
int main(){
freopen("cubicp.in","r",stdin);
freopen("cubicp.out","w",stdout);
for(int i = 1;i <= 1000002;i++) x[i] = (ULL)i*i*3+i*3+1;
scanf("%d",&T);
while(T--){
ULL a;
a = read();
if(check(a)) printf("YES\n");
else printf("NO\n");
}
return 0;
}


T3 猜数字

题目描述

LYK在玩猜数字游戏。
总共有n个互不相同的正整数,LYK每次猜一段区间的最小值。形如[li,ri]这段区间的数字的最小值一定等于xi。
我们总能构造出一种方案使得LYK满意。直到…… LYK自己猜的就是矛盾的!
例如LYK猜[1,3]的最小值是2,[1,4]的最小值是3,这显然就是矛盾的。
你需要告诉LYK,它第几次猜数字开始就已经矛盾了。


输入格式(number.in)

第一行两个数n和T,表示有n个数字,LYK猜了T次。
接下来T行,每行三个数分别表示li,ri和xi。


输出格式(number.out)

输出一个数表示第几次开始出现矛盾,如果一直没出现矛盾输出T+1。


输入样例
20 4
1 10 7
5 19 7
3 12 8
1 20 1


输出样例
3


数据范围

 对于50%的数据n<=8,T<=10。
对于80%的数据n<=1000,T<=1000。
对于100%的数据1<=n,T<=1000000,1<=li<=ri<=n,1<=xi<=n(但并不保证一开始的所有数都是1~n的)。

emmmmmmm

瞥了一眼像是线段树,区间赋值+最小值。。。(线段树印象淡化,代码自行脑补),我又问了问syp大佬,他说正解也可以是并查集,类似于code[vs]上的数轴染色。(有道理,emmmmmm


上午毕竟是信心题。。。


下午==>

T1 水题

题目描述

LYK 出了道水题。
这个水题是这样的:有两副牌,每副牌都有 n 张。
对于第一副牌的每张牌长和宽分别是 xi 和 yi。 对于第二副牌的每张牌长和宽分别是 aj和 bj。第一副牌的第 i 张牌能覆盖第二副牌的第 j 张牌当且仅当 xi>=aj 并且 yi>=bj。 (注意牌不能翻转)当然一张牌只能去覆盖最多一张牌,而不能覆盖好多张。
LYK 想让两副牌的各 n 张一一对应叠起来。 它想知道第二副牌最多有几张能被第一副牌所覆盖。


输入格式(water.in)

第一行一个数 n。
接下来 n 行,每行两个数 xi,yi。
接下来 n 行,每行两个数 aj,bj。


输出格式(water.out)

输出一个数表示答案。


输入样例

3
2 3
5 7
6 8
4 1
2 5
3 4


输出样例

2


数据范围

对于 50%的数据 n<=10。
对于 80%的数据 n<=1000。
对于 100%的数据 1<=n<=100000,1<=xi,yi,aj,bj<=10^9。

emmmmm

multiset大法好!!
一看就是贪心,显然被覆盖的另一张牌越接近覆盖它的牌越好。
首先把牌按照x从小到大排序,从前往后枚举,碰到第二副牌就扔进multiset,碰到第一副牌就在multiset中找与它y最接近的(当然要满足小于等于y);
multiset大法好!!!扔个链接multiset用法及相关操作


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<set>
using namespace std;
const int range = 100000+5;
struct H {
int x,y;
int type;
}a[range*2];
bool cmp(const H & a,const H & b){
if(a.x == b.x) return a.type>b.type;
return a.x < b.x;
}
multiset<int> ms;
int n,ans;
int main(){
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= 2*n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].type = i>n?1:0;
}
sort(a+1,a+1+2*n,cmp);
for(int i = 1;i <= 2*n;i++){
if(a[i].type) ms.insert(a[i].y);
else{
multiset<int>::iterator it;
it = ms.upper_bound(a[i].y);
if(it == ms.begin()) continue;
ms.erase(--it);
ans++;
}
}
printf("%d\n",ans);
return 0;
}

T2 梦境

题目描述

LYK 做了一个梦。
这个梦是这样的,LYK 是一个财主,有一个仆人在为 LYK 打工。
不幸的是,又到了月末,到了给仆人发工资的时间。但这个仆人很奇怪,它可能想要至少 x 块钱,并且当 LYK 凑不出恰好 x 块钱时,它不会找零钱给 LYK。
LYK 知道这个 x 一定是 1~n 之间的正整数。 当然抠门的 LYK 只想付给它的仆人恰好 x 块钱。但 LYK 只有若干的金币,每个金币都价值一定数量的钱(注意任意两枚金币所代表的钱一定是不同的,且这个钱的个数一定是正整数) 。LYK 想带最少的金币,使得对于任意 x,都能恰好拼出这么多钱。并且 LYK 想知道有多少携带金币的方案总数。
具体可以看样例。


输入格式(dream.in)

第一行一个数 n,如题意所示。


输出格式(dream.out)

 输出两个数,第一个数表示 LYK 至少携带的金币个数,第二数表示方案总数。


输入样例

6

输出样例

3 2

样例解释

LYK 需要至少带 3 枚金币,有两种方案,分别是{1,2,3},{1,2,4}来恰好得到任意的 1~n 之间的 x。


输入样例 2

10

输出样例 2

4 8


数据范围

对于 30%的数据 n<=10。
对于 60%的数据 n<=100。
对于 100%的数据 n<=1000。

emmmmmm

本蒟蒻对动规有着天生的抵触情绪(假装不高兴
第一问可以打表找规律,cnt = log2(n)+1;
f[i][j][k]表示前i个数字,和为j,最大的数位k;f[i+1][min(p+j,n)][p] += f[i][j][k];其实方程还是很好想的,可能是平常基本不做动规的题,看见动规就头疼,有dalao告诉我,dp的题可以用搜索拿部分分。rp++······

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
int f[2][1005][1005];
int n,ans,cnt;
int main(){
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
scanf("%d",&n);
cnt = (int)log2(n)+1;
f[0][1][1] = 1;
for(int i = 1;i <= cnt;i++)
for(int j = 1;j <= n;j++)
for(int k = 1;k <= n;k++)
if(f[(i+1)%2][j][k])
for(int p = k+1;p <= j+1;p++)
f[i%2][min(p+j,n)][p] += f[(i+1)%2][j][k];
for(int i = 1;i <= n;i++) ans += f[(cnt+1)%2][n][i];
printf("%d %d",cnt,ans);
return 0;
}

Markdown

更早的文章

第K小数

题目描述 有两个正整数数列,元素个数分别为N和M。从两个数列中分别任取一个数相乘,这样一共可以得到NM个数,询问这NM个数中第K小数是多少。 输入格式 输入文件名为number.in。输入文件包含三行。第一行为三个正整数N,M和K。第二行为N个正整数,表示第一个数列。第三行为M个正整数,表述第二个 …

于  二分答案 继续阅读