代码源Div2 604-706

604 碰撞2

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

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

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

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

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

输入格式

​ 第一行一个整数 N ；

​ 接下来 N  行，每行两个整数 Xi  和 Yi ，表示第 i  个人的位置；

​ 最后一行是一个由 L 和 R 组成的长为 N  的字符串 S 。

输出格式

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

样例输入 1

3
2 3
1 1
4 1
RRL

样例输出 1

Yes

样例输入 2

2
1 1
2 1
RR

样例输出 2

No

样例输入 3

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

样例输出 3

Yes

数据规模

​ 所有数据保证 2≤N≤2×1e5 ，0≤Xi≤1e9 ，0≤Yi≤1e9 。

思路：

        题目中的人只左右走也就是平行于x轴，所以对于y轴不同的分别考虑。在一行中，靠左的人向右走，靠右的向左走，则一定会碰上，否则不会碰上。

        那么将输入的数据排序后，从前往后遍历，出现向右走的人标记一下，记录其所在的 y 轴，遇到向左走的人时，比较二者的y轴是否相等，相等表明在同一行，一定相撞；遍历结束仍未出现这种情况则说明这群人不会碰撞。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
struct node
{int x,y;char f;
}a[N];
bool cmp(node a,node b)
{if(a.y==b.y) return a.x<b.x;return a.y<b.y;
}
int s[N];
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n;cin>>n;for(int i=1;i<=n;++i)cin>>a[i].x>>a[i].y;for(int i=1;i<=n;++i)cin>>a[i].f;sort(a+1,a+n+1,cmp);int p=0;int k=0;bool f=0;for(int i=1;i<=n;++i){if(a[i].f=='R') k=i,f=1;if(a[i].f=='L'&&a[i].y==a[k].y&&f!=0){p=1;}}if(p==1) cout<<"Yes"<<'\n';else cout<<"No"<<'\n';return 0;
}

605 优美！最长上升子序列

多组数据。

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

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

i1∣i2∣i3∣⋯∣ik 

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

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

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

输入格式

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

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

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

输出格式

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

数据规模

• 1≤T≤100 
• 1≤N≤1e6 ,但保证 ∑(T,i=1)Ni≤1e6 
• 1≤Ai≤1e9 

样例输入

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

样例输出

3
1
4
1

解释：

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

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

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

思路：

        套用LIS（最长上升子序列的思路），不过在比较更新时只枚举对应的倍数是否可行。

代码：

#include<bits/stdc++.h>
using namespace std;
int f[2000010];
int a[2000010];
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int T;cin>>T;while(T--){int n;cin>>n;int ans=1;for(int i=1;i<=n;++i){cin>>a[i];f[i]=1;}for(int i=1;i<=n;++i){for(int j=i*2;j<=n;j+=i){if(a[j]>a[i]){f[j]=max(f[j],f[i]+1);}ans=max(f[j],ans);}}cout<<ans<<'\n';}return 0;
}

606 巨大的牛棚

题目描述

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

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

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

输入描述

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

输出描述

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

样例输入

8 3
2 2
2 6
6 3

样例输出

5

思路：

        二维动态规划。

对没种树的的格子来说，它的递推式为

                 f [ i ][ j ] = min ( f [ i ] [ j - 1 ] , min ( f [ i - 1 ] [ j ] , f [ i - 1 ] [ j - 1 ] ) ) + 1 ;

代码：

#include<bits/stdc++.h>//二维动归 
using namespace std;
int m[1010][1010];
int f[1010][1010];
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n;cin>>n;int T;cin>>T;for(int i=1;i<=T;++i){int a,b;cin>>a>>b;m[a][b]=1;}int ans=-1;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(!m[i][j])f[i][j]=min(f[i][j-1],min(f[i-1][j],f[i-1][j-1]))+1;ans=max(f[i][j],ans);}}cout<<ans<<'\n';return 0;
}

607 高利贷

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

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

给出小 L  贷款的原值为 n ，分期付款金额 m  和分期付款还清贷款所需的总月数 k ，求该贷款的月利率 p 。

输入格式

三个用空格隔开的正整数 n ，m ，k ，含义如上述所示。

输出格式

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

数据范围

1≤n,m≤1e6,1≤k≤300 

0≤p≤5, n≤m×k 

输入样例1

1000 1200 1

输出样例1

0.200000

输入样例2

1000 100 12

输出样例2

0.029229

样例解释

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

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

思路：

        在题中解释第二组样例时给出了计算公式，但由计算公式难以倒推出 p 的表达式，同时注意到当 p 越高时，最终还的钱越多，所以我们可以使用二分法来试出 p 的值。

        实型做二分时不能直接用 > 或 < 来比较，可以规定误差来判断是否找到答案，正巧题目中也给出了误差范围。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n,m,k;
bool check(double p)
{double sum=0;for(int i=1;i<=k;++i){sum+=(1.0*m/pow(1+p,i));}if(sum>(double)n) return false;//p大了 else return true;
}
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);cin>>n>>m>>k;//一个月m/(1+p)^k，求1~k月累加和//二分，sum>n,p--;sum<n,p++double l=0,r=5;while(l<r&&fabs(l-r)>=1e-8){double mid=(l+r)/2;if(check(mid)) r=mid;else l=mid;}cout<<fixed<<setprecision(6)<<l;return 0;
}
/*
*/

701 背包

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

cc希望将其中的一些物品放入他的背包中，他希望这些物品的体积之和至少是背包体积的一半，并且不超过背包的体积，即 ⌈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之间，直接取这一件就能满足题意；大于w的物品一定是不行的；小于w/2的物品，如果全加起来还不能超过w/2那也不行，否则因为这些物品本身<w/2，所以挑出其中几件一定可以在w/2和w之间。

        所以：1.有w/2到w之间的物品

                   2.小于w/2的物品相加超过w/2的

        这两种情况符合条件输出“YES”

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int N=2e5+10;
int a[N];
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int T;cin>>T;while(T--){int n;cin>>n;ll w;cin>>w;bool f=false;for(int i=1;i<=n;++i) cin>>a[i];sort(a+1,a+1+n,greater<int>());ll sum=0;for(int i=1;i<=n;++i){if(a[i]>w) continue;sum+=a[i];if(a[i]>=1.0*w/2||sum>=1.0*w/2){f=true;break;}}if(f) cout<<"YES"<<'\n';else cout<<"NO"<<'\n';}return 0;
}
/*
*/

702 三回文序列

给定一个长度为n 的序列a 。

我们定义三回文序列是形如

的序列，例如:[1,1,1,2,2,1,1,1] 是一个三回文序列，而[1,1,1,2,2,2,3,3,3],[1,1,2,2,1] 都不是三回文序列。

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

注意，k1,k2 可以为00

输入格式

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

对于每一个测试用例

第一行给出序列的长度n 

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

输出格式

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

数据范围

1≤t≤2000 1≤∑n≤2e5,1≤ai≤26 

样例输入

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

样例输出

7
2
4
1
1
3

思路：

        理解错题了，看的大佬的，贴上链接。

代码：

#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>#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")#define endl '\n';
typedef long long ll;
typedef pair<int, int> PII;int n;int change(vector<int>v, int ans, vector<int>nums)
{int l = 0, r = n - 1, cnt = 0, res = nums[ans];while (l < r){while (l < r && v[l] != ans){nums[v[l]]--;l++;}while (l < r && v[r] != ans){nums[v[r]]--;r--;}cnt += min(nums[ans], 2);nums[ans] -= 2;l++, r--;for (int i = 1; i <= 26; i++)res = max(res, cnt + nums[i]);}return res;
}int main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin >> t;while (t--){cin >> n;vector<int>v(n),nums(27);for (int i = 0; i < n; i++){cin >> v[i];nums[v[i]]++;}int res = 0;for (int i = 1; i < 27; i++){if (nums[i] != 0)res = max(res, change(v, i,nums));}cout << res << endl;}return 0;
}

703 简单的异或问题

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

输入格式

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

输出格式

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

样例输入

2 2

样例输出

3

样例解释

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

 思路：

异或的结论

        1.0~2^m-1的所有数xor后结果为零
        2.一个数异或0等于他本身
        所以有2^m-1 xor 2^m-1-a = a 时，再与 异或为零的几个数 异或结果不变。所以将剩下的几个在 {0,1,2,…,2m−1} 中的数都加进来以达到最大个数。

        查资料时发现了个没见过的异或说法：异或就是不进位的加法。感觉很好用，记一下。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long intint main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);ll n,m;cin>>n>>m;ll ans=1;ans<<=m;if(m==1&&n==0) cout<<1<<'\n';else if(m==1&&n==1) cout<<2<<'\n';else cout<<1LL*(ans-min(n,1LL))<<'\n';return 0;
}
/**/ 

704 子串的循环挪动

​ 给出一个字符串 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。

思路:

        直接转换时不好处理，则将要变换的区间在变换时赋给另一个数组，再将这个数组中重新赋给原数组完成转换。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long intint main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);char s[10010];char c[10010];cin>>s;int m;cin>>m;for(int i=1;i<=m;++i){int l,r,k;cin>>l>>r>>k;l--,r--;k%=r-l+1;for(int j=r-k+1;j<=r;++j)c[j]=s[j];for(int j=r-k;j>=l;--j)s[j+k]=s[j];for(int j=r-k+1,p=l;j<=r;++j,++p)s[p]=c[j];}cout<<s<<'\n';return 0;
}
/*
12345678
4-7 1
12374568
*/ 

705 弗拉德和糖果 II

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

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

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

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

输入格式：

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

输出格式:

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

样例输入

2
1 1

样例输出

YES

说明

只有两种情况：

1.

1 2

2.

2 1

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

数据限制

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

思路：

        对于一种糖果来说，只有一样和不一样两种糖果，那若不让相同的糖果在一起就在中间插入不同的糖果就行了，那就是判断不同种的糖果够不够插入，够就可以将同种的分开。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int N=5000010;
int a[N];
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n;cin>>n;ll sum=0;for(int i=1;i<=n;++i){cin>>a[i];sum+=a[i];}bool f=true;for(int i=1;i<=n;++i){if(a[i]>sum-a[i]+1) f=false; }if(f) cout<<"YES"<<'\n';else cout<<"NO"<<'\n';return 0;
}

706 上帝的集合

题目描述

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

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

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

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

输入描述

第一行输入一个整数 n；

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

1 xi

2 xi

3

输出描述

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

样例输入

7
1 2
1 1
3
1 3
2 5
3
3

样例输出

1
7
8

数据范围

2≤n≤10^6, 1≤xi≤10^12

思路：

       此题肯定不能一个一个加数，肯定会超时，我们可以在外面记录已经加多少了，对于插入的值可以先减去这个值再插入，查找的值可以加上这个值再输出，这样就可以保证加值时新插入的值也能保证顺序。

        优先队列可以将数按顺序排列，还能便捷地得到、插入、删除最值，简直完美。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
priority_queue <ll,vector<ll>,greater<ll> > q;
int main()
{ll sum=0;std::ios::sync_with_stdio(false);std::cin.tie(0);int n;cin>>n;for(int i=1;i<=n;++i){int op;cin>>op;if(op==1){ll x;cin>>x;q.push(x-sum);}if(op==2){ll x;cin>>x;sum+=x;}if(op==3){cout<<q.top()+sum<<'\n';q.pop();}}return 0;
}