A. Deletions of Two Adjacent Letters
一个字符串，长度为奇数（长度不大于 ），只可以在其中删除连续的两个字符。问是否能使删剩下的字符（必须删到一个字符）为给定字符？
能则输出 YES，不能则输出 NO。
如果这个字符处在偶数位上，那么他的左边或者右边就都有奇数个字符，不可能通过删去连续的两个字符来留下这个字符（左右不能跨分界线删除）。
注意同一个字符可能出现多次。模拟即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int a=-1,f=0;
string s1,s2;
cin>>s1>>s2;
for(int i=0;i<s1.length();i++)
if(s1[i]==s2[0])
if(i%2==0) {f=1;break;}
if(f) puts("yes");
else puts("no");
}
return 0;
}
|
B. DIV + MOD
定义函数 ，其中 为系数。
给定系数 ，给定 范围 ，求 在范围内值的最大值。
其中 ，。
显然在范围区间内变化大的是右边的 （为什么？）。
但也会出现 变化的情况。那么，最大值就有两种情况了（即两个大幅度的变化区间，下见图片）：
- 在小于等于 的数中除以 的余数最大。
- 数 。
那么，若存在情况 1，则取最大值。若不存在，直接取情况 2 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int l,r,a;
cin>>l>>r>>a;
int x=r/a*a-1;
if(x>=l) cout<<max(x%a+x/a,r%a+r/a)<<endl;
else cout<<r%a+r/a<<endl;
}
return 0;
}
|
C. Weight of the System of Nested Segments
在一个数轴上，有一些整点。称一些数为 包含系统 ，当这些坐标配对 时，任意 有 。
共有 个点，取出其中 个点，使得这些数配对 组后代价和最小。
一个配对的代价为 。
给出每个点的坐标 和代价 。求最小代价和和匹配数字的序号（序号就是输入的顺序，从 开始）。
不超过 。
只要取出 个点，都可以说明这些点可以配对（从左到右，从右到左依次配对）。
所以，我们只需要以代价排一遍序，左边取 个数，再以坐标为关键字排序配对即可。
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
| #include<bits/stdc++.h>
using namespace std;
struct Node{
int x,w,id;
}nd[200001];
vector<Node> ans;
bool cmp(Node a,Node b) { return a.w<b.w; }
bool cmp2(Node a,Node b) { return a.x<b.x; }
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,sum=0;
cin>>n>>m;
for(int i=1;i<=m;i++) nd[i].id=i;
for(int i=1;i<=m;i++) cin>>nd[i].x>>nd[i].w;
sort(nd+1,nd+m+1,cmp);
ans.clear();
for(int i=1;i<=n*2;i++) sum+=nd[i].w,ans.push_back(nd[i]);
cout<<sum<<endl;
sort(ans.begin(),ans.end(),cmp2);
for(int i=0;i<ans.size()/2;i++) cout<<ans[i].id<<" "<<ans[ans.size()-i-1].id<<endl;
}
return 0;
}
|