#671. 优美！最长上升子序列

附加文件统计

描述
提交
自定义测试

多组数据。

每组将给定一个数组。派派希望从中选择一个递增的子序列，越长越好。

但派派认为，这样选出来的子序列依然不够「优美」，形式化的讲，派派希望选择的下标（从 11 开始）需要满足

i1∣i2∣i3∣⋯∣iki1∣i2∣i3∣⋯∣ik

其中 a|ba|b 表示整除，即 aa 是 bb 的约数。

请你帮助派派完成任务吧！

注：子序列的含义不再赘述。

输入格式

第一行一个整数 TT，表示接下来有 TT 组数据。

每组数据包含两行，第一行包含一个整数 NN。

随后一行，包含 NN 个整数，表示原数组 {A}{A}。

输出格式

对于每组数据，输出一行，包含一个数，表示能选出的「优美」的最长上升子序列长度。

数据规模

1≤T≤1001≤T≤100
1≤N≤1061≤N≤106,但保证 ∑i=1TNi≤106∑i=1TNi≤106
1≤Ai≤1091≤Ai≤109

样例输入

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

样例输出

解释：

对于第一组数据，能选择的「优美」最长上升子序列为 {A1,A2,A4}={1,4,7}{A1,A2,A4}={1,4,7}。

对于第三组数组，选择 {A1,A2,A4,A8}={1,2,4,8}{A1,A2,A4,A8}={1,2,4,8}。

对于第四组数据，可选择的「优美」最长上升子序列长度为 11。

1.这道题用dp如果直接枚举再一个个判断下标，时间复杂度是o(n*n)会超时，那么我们直接在符合条件的下标里面进行寻找就行了

2.或者也可以用贪心的思想，时间复杂度也为o*log(n)，不过需要再另外开一个数组存储下标即可

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6+10;
int n, b[N], a[N];
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){memset(a, 0, sizeof a);memset(b, 0, sizeof b);int m,ans=1;scanf("%d", &m);for (int j = 1; j <= m; j++){scanf("%d", &a[j]);b[j] = 1;}int j;for ( j = 1; j <= m; j++){for (int k = 2 * j ;k<= m;k+=j){if (a[k] > a[j])b[k] = max(b[k], b[j] + 1);ans = max(ans, b[k]);}}printf("%d\n", ans);}return 0;
}

#705. 碰撞2

附加文件统计

描述
提交
自定义测试

在 xyxy 坐标系中有 NN 个人，第 ii 个人的位置是 (Xi,Yi)(Xi,Yi)，并且每个人的位置都不同。

我们有一个由 L 和 R 组成的长为 NN 的字符串 SS，Si=Si= R 代表第 ii 个人面向右，Si=Si= L 代表第 ii 个人面向左。

现在所有人开始朝着他们各自面向的方向走，即面向右 xx 就增，面向左 xx 就减。

例如，当 (X1,Y1)=(2,3),(X2,Y2)=(1,1),(X3,Y3)=(4,1),S=(X1,Y1)=(2,3),(X2,Y2)=(1,1),(X3,Y3)=(4,1),S= RRL 时，人们的移动如图。

我们把两个人对向行走到一个位置称为一次碰撞。请问如果人们可以无限走下去，会有人产生碰撞吗？

输入格式

第一行一个整数 NN；

接下来 NN 行，每行两个整数 XiXi 和 YiYi，表示第 ii 个人的位置；

最后一行是一个由 L 和 R 组成的长为 NN 的字符串 SS。

输出格式

如果会有碰撞，输出 Yes，否则输出 No。

样例输入 1

样例输出 1

Yes

样例输入 2

样例输出 2

No

样例输入 3

样例输出 3

Yes

数据规模

所有数据保证 2≤N≤2×1052≤N≤2×105，0≤Xi≤1090≤Xi≤109，0≤Yi≤1090≤Yi≤109。

需要注意能够碰撞的两个球不止要方向相反，且坐标小的球需要朝右边滚。-->联想到对坐标进行排序，在一个个判断方向

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int N = 2e5 + 1;
struct aa {int x;int y;int cnt;
}a[N];
typedef struct aa ST;bool cmp (ST a, ST b) {if (a.y != b.y)return a.y < b.y;return a.x < b.x;
}char s[N];
int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d%d", &a[i].x, &a[i].y);a[i].cnt = i;}scanf("%s", s);sort(a, a + n, cmp);for (int i = 0; i < n - 1; i++) {if (a[i].y == a[i + 1].y) {if (s[a[i].cnt] == 'R' && s[a[i + 1].cnt] == 'L') {printf("Yes\n");return 0;}}}printf("No\n");return 0;
}

#708. 高利贷

附加文件统计

描述
提交
自定义测试

19岁的大学生小 LL 家里情况不好，每月固定生活费不足以买一部苹果手机。当他得知有贷款机构可以贷小额贷款并且可以分期等额还款，每月只需要还几百块时，在虚荣心的驱使下他开始自己的贷款之旅。

贷款机构声称利率按月累计，贷款人在贷款期间每月偿还固定的分期付款金额。

给出小 LL 贷款的原值为 nn，分期付款金额 mm 和分期付款还清贷款所需的总月数 kk，求该贷款的月利率 pp。

输入格式

三个用空格隔开的正整数 nn，mm，kk，含义如上述所示。

输出格式

一个实数 pp，表示该贷款的月利率（用小数表示），和标准输出绝对值不超过10−610−6即可。

数据范围

1≤n,m≤106,1≤k≤3001≤n,m≤106,1≤k≤300

0≤p≤5,0≤p≤5,

n≤m×kn≤m×k

输入样例1

1000 1200 1

输出样例1

0.200000

输入样例2

1000 100 12

输出样例2

0.029229

样例解释

对于第一组样例，小 LL 贷款了 10001000 元，并在一个月后支付 12001200 元还清了贷款。因此计算月利率 pp 的公式为 1000×(1+p)=12001000×(1+p)=1200 或 12001+p=100012001+p=1000，求出 p=0.200000p=0.200000。

对于第二组样例，小 LL 贷款了 10001000 元，并以每月支付 100100 元的方式在 1212 个月后还清了贷款。由于月利率的存在，他第 kk 个月偿还的金额只相当于 100(1+p)k100(1+p)k 元的初始金额，且这12个月共偿还初始金额1000元，求出 p=0.029229p=0.029229。

用等比数列前n项和公式不能直接推导出一个一次等式，有点复杂。这种有点奇怪的题一般就用二分做了。注意用一个合适的二分板子，以及浮点数的

比较

#include<iostream>
using namespace std;
int n, m, k;
double ans;
int check(double mid,double mm)
{double res = 0, p=1.0+mid;for (int i = 1; i <= k; i++){res += mm/p;p *= (1.0 + mid);if (res > (double)n)return 1;}return 0;
}
int main()
{cin >> n >> m >> k;double l = 0, r = 5;while (r - l >= 1e-8){double mid = (l + r) / 2.0;if (check(mid,m))l = mid;else r = mid;}printf("%.6lf", l);return 0;
}

#706. 巨大的牛棚

附加文件统计

描述
提交
自定义测试

题目描述

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 n * n的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。考虑下面的方格，它表示农夫约翰的农场，‘.'表示没有树的方格，‘#'表示有树的方格

........
.#...#..
........
........
........
..#.....
........
........

那么最大的牛棚是5*5的。

输入描述

第一行输入一个正整数 n(1≤n≤1000)n(1≤n≤1000)代表农场的大小，一个正整数T(1≤T≤n∗n)T(1≤T≤n∗n)，接下来 TT 行，每行2个整数，代表有树的格子的横纵坐标，保证任意两个树格子不相同

输出描述

输出一个正整数代表牛棚的最大边长

样例输入

样例输出

1.二分答案，枚举可能的最大边长，然后判断题目给的矩阵能不能找到满足我们枚举长度的正方形，不过一一枚举肯定会超时。

2.需要用到矩阵前缀和，sum[i][j],表示i,j左上方区域值的和，mp[i][j]表示该点的值，初始化sum[i][j] = sum[i - 1][j] + sum[i][j-1] - sum[i - 1][j - 1] + mp[i][j];

3.注意下标范围

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int mp[N][N],t,n,sum[N][N],ans;
int check(int mid)
{int res = 0;for (int i = 1; i + mid-1 <= n; i++){for (int j = 1; j + mid-1 <= n; j++){res = 0;res += sum[i + mid - 1][j + mid - 1] - sum[i + mid - 1][j-1] - sum[i-1][j + mid - 1] + sum[i-1][j-1];if (res == 0)return 1;}}return 0;
}
int main()
{scanf("%d", &n);scanf("%d", &t);while (t--){int x, y;scanf("%d%d", &x, &y);mp[x][y] = 1;}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){sum[i][j] = sum[i - 1][j] + sum[i][j-1] - sum[i - 1][j - 1] + mp[i][j];}}int l = 1, r = n;while (l <= r){int mid = (l + r) / 2;if (check(mid))ans = mid, l = mid + 1;else r = mid - 1;}cout << ans;return 0;
}

三回文序列

附加文件统计

描述
提交
自定义测试

给定一个长度为nn的序列aa。

我们定义三回文序列是形如a...ak1a...a⏟k1b...bk2b...b⏟k2a...ak1a...a⏟k1的序列，例如:[1,1,1,2,2,1,1,1][1,1,1,2,2,1,1,1]是一个三回文序列，而[1,1,1,2,2,2,3,3,3],[1,1,2,2,1][1,1,1,2,2,2,3,3,3],[1,1,2,2,1]都不是三回文序列。

现在，希望你找到序列aa中最长的三回文序列的长度。

注意，k1,k2k1,k2可以为00

输入格式

第一行给出一个数字TT，表示TT组测试用例

对于每一个测试用例

第一行给出序列的长度nn

第二行给出序列a1,a2,a3...ana1,a2,a3...an

输出格式

对于每一个测试用例，输出最长的三回文序列的长度。

数据范围

1≤t≤20001≤t≤20001≤∑n≤2e5,1≤ai≤261≤∑n≤2e5,1≤ai≤26

样例输入

1.把数组分为左边，右边和中间三部分。

2.使得左边和右边部分的当前枚举数字个数相同

3.取中间其他数字的最大数量

4.特判左右指针重合的情况

6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1

样例输出

#include<iostream>
#include<cstring>
using namespace std;
int t, n;
const int N = 2e5 + 10;
int a[N],s[30][N];
int main()
{scanf("%d", &t);while (t--){int ans = 0;scanf("%d", &n);memset(a, 0, sizeof a);memset(s, 0, sizeof s);for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= 26; i++)//计算前缀和for (int j = 1; j <= n; j++)s[i][j] = s[i][j - 1] + (a[j] == i);//s[i][j]表示前j位含有多少个ifor (int i = 1; i <= 26; i++)//枚举每个数字{int l = 0, r = n+1, cnt1 = 0,cnt2=0;//这里l、r赋值分别减一和加一是因为下面while循环l++,r--;for (int j = 1; j <= n; j++)//枚举长度{while (cnt1 <j && l < r)//分别移动左右指针l++, cnt1+=(a[l]==i);//等于枚举的数i就计数加1while (cnt2 <j && l < r)r--, cnt2+=(a[r]==i);if (cnt1 != j || cnt2 != j)break;//左右两边枚举长度不相等for (int k = 1; k <= 26; k++)//枚举(i-r)中间串的最大长度{if (l < r)ans = max(ans, j * 2 + s[k][r - 1] - s[k][l]);elseans = max(ans, j * 2 - 1);//有一个交叉重复部分}}}printf("%d\n", ans);}return 0;
}

这是4月9日代码源div2的每日一题。

背包 - 题目 - Daimayuan Online Judge

cc有一个背包，背包的体积为w，有n个物品，每一个物品的体积为ai

cc希望将其中的一些物品放入他的背包中，他希望这些物品的体积之和至少是背包体积的一半，并且不超过背包的体积，即 ⌈w/2⌉≤sum≤w⌈w/2⌉≤sum≤w

请你帮cc判断这些物品中有没有符合条件的物品组合，如果有输出"YES", 没有输出"NO"

cc至少会拿一个物品

输入格式

第一行给出测试样例个数T

对于每一个样例:

第一行给出一个n和一个w，n个物品,背包的总体积是w

第二行给出一个序列a1,...an，代表每一个物品的体积

输出格式

如果有请输出"YES", 没有输出"NO"

数据范围

1≤t≤1e4 ，1≤∑n≤2e5,1≤w≤1e18 0≤wi≤1e9

样例输入1

3
1 3
3
6 2
19 8 19 69 9 4
7 12
1 1 1 17 1 1 1
复制代码

样例输出

YES
NO
YES
复制代码

问题解析

遍历一下他给的物品，小于等于背包体积一半的都装背包里，不满足条件的直接看那个货物是不是就在w/2~w之间。

首先你小于一半的装背包里，当你背包已经装了一半的时候已经满足条件了，不满足一半的时候你装一个小于一半的肯定也不会超。
链接：https://juejin.cn/post/7084524808670543903

#include<iostream>
using namespace std;
#include<vector>
#define endl '\n';
typedef long long ll;
int main()
{int t;cin >> t;while (t--){ll n, m;cin >> n >> m;ll res = 0;vector<ll>v(n);bool flag = false;for (int i = 0; i < n; i++){cin >> v[i];if (!flag&&v[i] >= (m + 1) / 2 && v[i] <= m){cout << "YES" << endl;flag = true;}}if (flag)continue;for (int i = 0; i < n; i++){if (v[i] < (m + 1) / 2){res += v[i];}if (res >= (m+1) / 2 && res <= m){flag = true;cout << "YES" << endl;break;}if (res > m)break;}if (!flag)cout << "NO" << endl;}return 0;
}

#732. 简单的异或问题

附加文件统计

描述
提交
自定义测试

有一组整数 {0,1,2,…,2m−1}{0,1,2,…,2m−1}, 请从中选出 kk 个数，使得这 kk 个数的异或和为 nn, 请输出最大的满足条件的 kk。

输入格式

两个数 nn 和 mm, 其中 0≤n≤2m−1,1≤m≤600≤n≤2m−1,1≤m≤60。

输出格式

输出最大的满足条件的 kk。

样例输入

2 2

样例输出

样例解释

对于样例，我们可以选择 {0,1,3}{0,1,3}。

1.这k个数的二进制的每一位上进行的都是异或运算,因为异或运算，同为1异或后为零，仅有1个1异或后为0，也就是说，偶数个1异或后为0，奇数个1异或后为1，经证明知当m不为1时，从0到 $2^{m}-1$ 的每个数的二进制的各个位上的1相加都为偶数。

2.所以当m!=1时，将这些数都异或后都为0

3.由于0^x=x，x^x=0，所以只要在这些数字中不选数字n即可,因为所有不选数字n的数异或和一定为n,这样结果才会是0（n^n=0).

4.经过调整后发现，要调整的01序列，其实就是最后异或得出的n的二进制表示，所以将除去n之外的所有数进行异或就得到了n，则其异或的个数的最大值k=个.比较特殊的情况是，当n=0时，因为0的二进制表示的每一位都为0，因此将0减去后异或的数与不减去0异或后的数相等，而题目要求的k是最多的异或个数，故当n=0时，k=个，当m=1时，则需要另外进行特判。

原文链接：https://blog.csdn.net/ChuRi_BaiYu/article/details/124601685

#include<iostream>using namespace std;long long cj(long long m)
{long long ans=1;for(int i=1;i<=m;i++)   ans=ans<<1;return ans;
}int main()
{long long n,m;cin >>n >>m;if(n!=0&&m!=1)  cout <<(cj(m)-1) <<endl;else if(n==1&&m==1) cout <<2 <<endl;else if(n==0&&m==1) cout <<1 <<endl;else cout <<cj(m) <<endl;return 0;
}

知识点：字符串

子串的循环挪动 - 题目 - Daimayuan Online Judge

给出一个字符串 s，你需要执行 m 个任务。每个任务给出两个下标 li,ri和一个整数 ki（字符串的下标从 1 开始），表示你需要循环挪动 s 的子串 s[li...ri] ki 次。请从前到后依次执行给出的每个任务。

字符串的循环挪动操作：将最后一个字符移到第一个字符的位置，并且将其他所有字符向右移一个位置。

比如：如果字符串 s 是 abacaba，一个任务为 l1=3,r1=6,k1=1，那么答案为 abbacaa。接下来一个任务为 l2=1,r2=4,k2=2，那么我们会得到 baabcaa。

输入格式

第一行一个字符串 s，该字符串只包含小写英文字符。

第二行一个整数 m，表示任务个数。

接下来 m 行每行有三个整数 li,ri 和 ki。

输出格式

输出执行了 m 个任务后的最终的字符串 s。

样例输入

abacaba
2
3 6 1
1 4 2
复制代码

样例输出

baabcaa
复制代码

数据规模

对于所有数据保证，1≤|s|≤10000（|s| 表示字符串 s 的长度），1≤m≤300，1≤li≤ri≤|s|，1≤ki≤1000000

问题解析

每次进行移动，字符串会被分成三部分：s的头部，需要挪动的子串s2，s的尾部。然后我们知道，挪动k次，就相当于把长度为k的字符串从尾部挪去头部，所以我们也可以把需要挪动的子串分成两部分，长度为k的s2尾部子串（将要挪去前面的那部分），和将要从前面移动到后面的s2的头部子串，所以我们整体可以把字符串分成三部分：

s的头部s1，需要挪动的子串的头部s2，需要挪动的子串的尾部s3，s的尾部s4

此时s还是s1+s2+s3+s4。经过挪动后就变成了s1+s3+s2+s4（因为s3要挪到s2的前面）。那我们就分别获取这四段字符串，再拼接起来即可。

AC代码

这个拼接字符串的思路妙啊

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int MOD = 1e9 + 7, N = 1e6 + 10;int main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string str;cin >> str;int m,n=str.size();cin >> m;while (m--){int l, r, k;cin >> l >> r >> k;int mod = (r - l + 1);string s1 = str.substr(0, l-1);string s2 = str.substr(l - 1, r - l - (k % mod) + 1);string s3 = str.substr(r-k%mod, k%mod);string s4 = str.substr(r, n - r + 1);if(l!=r)str = s1 + s3 + s2 + s4;}cout << str << endl;return 0;
}

链接：https://juejin.cn/post/

#736. 上帝的集合

附加文件统计

描述
提交
自定义测试

题目描述

现在上帝有一个空集合，现在他命令你为他执行下列三种操作 nn 次，他每次会给你一个操作类型 opop。

操作1：向集合中插入一个整数 xx;

操作2：将集合中所有的数加上 xx;

操作3：输出集合中最小的数，并从集合中将他删除，如果存在多个最小的整数，任意选择一个即可;

输入描述

第一行输入一个整数 nn；

接下来的 nn 行，每行的输入如下所示。第一个数代表 opop，如果 op=1op=1 或 op=2op=2，第二个数代表 xixi：

11 xixi

22 xixi

输出描述

如果 op=3op=3，请输出集合中的最小值。

样例输入

样例输出

1
7
8

数据范围

2≤n≤1062≤n≤106, 1≤xi≤1012

7085697160091533326

用优先队列进行排序，对于操作二，只需用一个数add记录前面操作累计需要加上的数，进入队列的时候减去该数，最后输出的时候再加上更新后的add即可

#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
ll n, op, x, add;
int main()
{priority_queue<ll, vector<ll>, greater<ll>>q;scanf("%lld", &n);while (n--){scanf("%lld", &op);if (op == 1){scanf("%lld", &x);q.push(x - add);}else if (op == 2){scanf("%lld", &x);add += x;}else{printf("%lld\n", q.top() + add);q.pop();}}return 0;
}

#677. 弗拉德和糖果 II

附加文件统计

描述
提交
自定义测试

不久前，弗拉德过生日，他收到了一包糖果。有 nn 种糖果，第 ii 种糖果有 aiai 个（1≤i≤n1≤i≤n）。

弗拉德决定每次只吃一个糖果。为了从吃东西中获得最大的乐趣，弗拉德不想连续吃两个相同类型的糖果。

帮助他弄清楚他是否可以在不连续吃两个相同的糖果的情况下吃掉所有的糖果。

简而言之，给定 nn 个正整数 aiai，aiai 表示有 aiai 个 ii，找到是否存在一种序列，使得所有的数都用上，且不存在 ii 连续的情况

输入格式：

第一行，包含一个整数 nn。第二行，包含 nn 个正整数。

输出格式:

输出一行，如果存在，输出YES，否则输出NO

样例输入

2
1 1

样例输出

YES

说明

只有两种情况：

1 2

2 1

无论先吃哪种糖果，都能吃完且不连续吃相同类型的糖果

数据限制

对于 100%100% 的数据，保证 1≤n≤5000000,1≤ai≤230

出乎意料的思维题目...

(229条消息) 2022-04-13每日刷题打卡_#677. 弗拉德和糖果 ii_你好_Ä的博客-CSDN博客

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int MOD = 1e9 + 7, N = 1e6 + 10;inline int read() {int x = 0; char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x;
}int main()
{int n;ll sum = 0, mx = 0,num;n = read();for (int i = 0; i < n; i++){num = read();if (mx < num){sum += mx;mx = num;}else sum += num;}if ((n == 1 && mx == 1) || mx <= sum + 1){puts("YES");}else{puts("NO");}return 0;
}