A. 险恶的迷宫 https://www.cometoj.com/contest/73/problem/A
题意: 在二维平面坐标内, 给出一个圆心坐标 (a,b), 以及圆的半径 r , 再给出 n 个点的坐标 (x_i,y_i), 求有多少点在圆内.
数据范围: 0 < n <= 1e5, 0<r , x , y <=1e9
思路: 对于判断距离根据勾股定理: sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) <= r , 即在圆的范围内. 由于此题数据较大, sqrt 可能导致精度损失, 所以直接开 long long 进行平方比较 :(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2 )<= r*r;
- #include <bits/stdc++.h>
- typedef long long ll;
- using namespace std;
- const int maxn = 1e5+7;
- int main(){
- int n;
- ll a,b,r;
- cin>>n>>a>>b>>r;
- int ans = 0;
- for(int i=1;i<=n;i++){
- ll x,y;
- cin>>x>>y;
- if((x-a)*(x-a)+(y-b)*(y-b)<=r*r) ans++;
- }
- cout<<ans<<endl;
- }
B. 夕日的光辉 https://www.cometoj.com/contest/73/problem/B
题意: 给出长为 n 的字符串 str . 找到 pink 的子串序列. 求符合条件组成的 pink 自序列, 相邻两个 ( 比如 p 与 i 互相相邻, n 与 k 互相相邻 ) 最大坐标差 - 1
思路: 贪心: 求 p-i 间隔最大时, i-n 间隔最大时, n-k 坐标间隔最大时. 比如要使 p-i 坐标差最大, 即 p 取其能取道的最左边, i 取其符合条件组成的最右边.
code:
- #include <bits/stdc++.h>
- typedef long long ll;
- using namespace std;
- const int maxn = 1e6+7;
- const int inf = 0x3f3f3f3f;
- int p0[maxn];
- int p1[maxn];
- int p2[maxn];
- int p3[maxn];
- int fismin(int com,int p[],int len){
- // 找到第一个大于该数的位置
- for(int i=1;i<=len;i++){
- if(p[i]>com) return i;
- }
- // 没找到返回 0
- return 0;
- }
- int fismax(int com,int p[],int len){
- // 找到最后一个小于该数的位置
- if(p[len]<com) return len;
- else{
- for(int i=1;i<=len;i++){
- if(p[i]>com) return i-1;
- }
- return len;
- }
- }
- int main(){
- int T;
- cin>>T;
- string s;
- while(T--){
- int len;
- cin>>len;
- cin>>s;
- int f0,f1,f2,f3;
- f0 = f1 = f2 = f3 = 0;
- //p-i 间隔最大
- for(int i=0;i<len;i++){
- if(s[i]=='p') p0[++f0] = i;
- if(s[i]=='i') p1[++f1] = i;
- if(s[i]=='n') p2[++f2] = i;
- if(s[i]=='k') p3[++f3] = i;
- }
- int ans = -1;
- if(f0&&f1&&f2&&f3){
- int ff1,ff2;
- //1.p0 最左边, p3 最右边, p2 仅此 p3 右, p1 仅此 p2 右 p0-p1
- ff2 = fismax(p3[f3],p2,f2);
- if(ff2){
- ff1 = fismax(p2[ff2],p1,f1);
- if(ff1) ans = max(ans,p1[ff1]-p0[1]);
- }
- //2.po 最左边, p1 仅次 p0 左, p3 最有, p2 仅存 p3 右 p1-p2
- ff1 = fismin(p0[1],p1,f1);
- ff2 = fismax(p3[f3],p2,f2);
- if(ff1&&ff2){
- ans = max(ans,p2[ff2]-p1[ff1]);
- }
- //3.p0 左, p1 仅此左, p2 仅此左, p3 最右
- ff1 = fismin(p0[1],p1,f1);
- if(ff1){
- ff2 = fismin(p1[ff1],p2,f2);
- if(ff2) ans = max(ans,p3[f3]-p2[ff2]);
- }
- if(ans<0) cout<<-1<<endl;
- else cout<<ans-1<<endl;
- }else{
- cout<<-1<<endl;
- }
- }
- }
- View Code
C. 序列 https://www.cometoj.com/contest/73/problem/C
题意: 初始长为 n 的 0 序列, 进行 m 次操作. 每次操作给出区间 (l,r) , 将编号为奇数的序列 区间内的数字全部改成 第 i 次 操作的 i . 同时在每一次操作前, 把所有的序列复制一份.(如果还没理解题意, 可以看下原题样例解析)
求每次操作后的极大连续段的个数总和.
思路: 计数问题: 由于是统计极大连续段 (连续子区间) 个数, 所以我们可以 像 dp 计数一样, 记录 以 x 位置结束 (右端) 的连续子区间个数 f [x]. 比如初始时 长为 3 的 0 序列, f[3] = 1;
对于每次区间更改: 我们可以知道 (l-1) 与 l ,(r+1)与 r 的值肯定不一样, 所以每次修改操作后 f[l-1] 与 f [r]的贡献值会增大, 而增加的个数则是倍增的个数, 即第 i 次操作时 2^(i-1).
对于没有修改的位置的贡献, 由于每次倍增, 所以统计个数时就将其乘以 2.
最后统计答案, 就把所有位置的贡献相加即可.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn=2019;
- const ll mod=20050321;
- int n,m;
- ll f[maxn],p[maxn];
- // 定义 fx 表示的序列中, 存在极大连续段右端点为 x 的序列个数
- //x = n,a_x != a_x+1,
- // 每一次不同的统计在于从 1-n 此时所有的值的贡献
- // 由于每次对 l,r 操作后的值不同, 又每次更新 2^(i-1)个序列贡献, 所以 fr = fr + 2^(i-1);
- // 由于 1~i-1 与 r+1~n 的部分元素没有改变, 所以贡献翻倍
- int main()
- {
- cin>>n>>m;
- // 预处理 2^(i-1)
- p[0]=1;for(int i=1;i<=m;i++)p[i]=(p[i-1]*2)%mod;
- f[n]=1;
- for(int i=1;i<=m;i++)
- {
- int l,r;
- cin>>l>>r;
- for(int j=1;j<l-1;j++) f[j]=(f[j]*2)%mod;
- for(int j=r+1;j<=n;j++) f[j]=(f[j]*2)%mod;
- f[l-1]=(f[l-1]+p[i-1])%mod;
- f[r]=(f[r]+p[i-1])%mod;
- ll ans=0;
- for(int j=1;j<=n;j++) ans=(ans+f[j])%mod;
- cout<<ans<<endl;
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3280342.html