|
A. Strange Table
分析：
这是一道简单的签到题，可以通过找规律轻松写出。我们可以首先找到所在数字的列c，用x去除以n,如果能整除，那么x所在列c=x/n;否则c=x/n+1;然后很轻松可以发现，如果x能整除n,那么n*m=x,所以r=n；如果不能整除，那么 r=x-(c-1) * n ;
最后答案ans=(r-1) * m+c ;
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,x;
int main(){
cin>>t;
while(t--){
scanf("%lld %d %lld",&n,&m,&x);
ll r,c;
if(x%n==0) c=x/n,r=n;
else c=x/n+1,r=(x-(c-1)*n);
cout<<((r-1)*m*1ll+c)<<endl;
}
return 0;
}
B. Partial Replacement
分析：
限制条件有3条，前2条很容易满足。我们只需要从头遍历一遍找到第一个 * 并赋值为x,再从尾再遍历一遍找到第一个 * 并赋值为x即可；记得答案ans++。对于限制条件3，我们可以从头开始遍历，若遇到了x,我们便遍历当前位置pos到min(pos+k,n)（为了防止越界，取最小值）之间的数看看是否有x,若有，则将pos赋值为当前位置，并且跳出这个内循环；若没有，则将最后面的 * 的位置赋值为x,答案ans++;
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int t,k,n;
char s[55];
int main(){
cin>>t;
while(t--){
int ans=0,flag=0,pos=0;
scanf("%d %d",&n,&k);
scanf("%s",s+1);
for(int i=1;i<=n;i++)
if(s[i]=='*'){
s[i]='x';
ans++;
break;
}
for(int i=n;i>=1;i--){
if(s[i]=='*'){
s[i]='x';
ans++;
break;
}
}
for(int i=1;i<=n;i++){
if(s[i]=='*'||s[i]=='.') continue;
if(s[i]=='x'){
int flag=0,pos=0;
int p=min(i+k,n);
for(int j=i+1;j<=p;j++){
if(s[j]=='*') pos=j;
if(s[j]=='x') {
pos=j;flag=1;break;}
}
if(flag||!pos) continue;
else {s[pos]='x';ans++;}
}
}
cout<<ans<<endl;
}
return 0;
}
C. Double-ended Strings
分析：
由于这道题要求两个字符串最少删除多少个字符后相同，我们可以采用逆向思维。首先用 len 记录两个字符串的和，该和也将是可以删除的最大字符个数。由于数据较小，我们然后可以暴力枚举两个字符串，找到两个字符串最长的相同字串长度ans。最后答案就是len-2*ans;
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int ans,t;
char a[24],b[24];
int main(){
cin>>t;
while(t--){
scanf("%s%s",a,b);
ans=-INF;
int len=strlen(a)+strlen(b);
int lena=strlen(a),lenb=strlen(b);
for(int i=0;i<strlen(a);i++){
for(int j=0;j<strlen(b);j++){
int x=i,y=j,cnt=0;
while(a[x]==b[y]&&x<lena&&y<lenb) x++,y++,cnt++;
ans=max(cnt,ans);
}
}
cout<<len-ans*2<<endl;
}
return 0;
}
D - Epic Transformation
分析：
本题需要求数组在进行一些列操作后剩余的元素个数，操作：一次性可以删除两个不同的数字（注意：两个被选中的数据必须不同），该操作可以实行不限次数，直到数组为空或者数组中没有满足条件的数据可以操作。
仔细分析不难发现，这也是一道类似A题的找规律题。
我们可以首先找到数组中重复次数最多的元素个数ans。
1. 如果ans<=n/2 ;那么答案就是n-(n/2) * 2;（为什么不直接为0呢？因为数组元素个数可能为奇数）。
2. 否则,答案就是n-(n-ans)* 2。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
int t,n,x;
int main(){
cin>>t;
while(t--){
scanf("%d",&n);
int a[n+4],ans=-INF,cnt=1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<n;i++){
if(a[i]==a[i+1]) cnt++,ans=max(ans,cnt);
else ans=max(ans,cnt),cnt=1;
}
if(ans<=n/2) cout<<n-(n/2)*2<<endl;
else cout<<n-(n-ans)*2<<endl;
}
return 0;
}
E. Restoring the Permutation
分析：
本题给出一段有特定的关系的序列，需要求该序列的（1~n）最大和最小序列
那么如何解决这道问题呢？我们可以用两个vector不定长数组s1,s2存储最后的答案最大序列和最小序列。那我们接下来应该怎么做呢？，我们可以预处理一下将所有a[i] != i的元素i用两个set集合s3,s4维护。从1~n遍历每一个元素，也就是找每一个元素分别在最大序列，和最小序列中的位置。然后对于给定的序列a[],我们可以发现这样的规律，即若a[i] ! =a[i-1] 那么无论是要求的最大序列还是最小序列，i号位置一定是a[i].(因为a[i]为前i项中的最大值,若a[i]!=a[i-1],那么a[i]一定大于a[i-1],i也就是重复元素a[i]的第一个位置，为了满足条件，该序列这个位置一定就是a[i] )。而对于其他位置，也就是a[i]==a[i-1]的位置我们可以分别处理最大序列和最小序列的元素位置。
- 对于最小序列： 第一个集合中的头迭代器元素就是可取的最小元素，直接赋值为s1[i]=*（s3.begin()）；然后在s3中删除这个元素。
- 对于最大序列：我们用二分查找的lower_bound()找到第一个大于a[i]的元素的前一个元素，也就是小于a[i]的最大元素，赋值s2[i]=该元素，然后在s4中删除中该元素。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
int t,n;
int main(){
cin>>t;
while(t--){
scanf("%d",&n);
int a[n+4],book[n+4];
vector<int>s1(n+1),s2(n+1);
set<int>s3,s4;
memset(book,0,sizeof(book));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
book[a[i]]=1;
if(a[i]!=i&&!book[i]) s3.insert(i),s4.insert(i);
}
for(int i=1;i<=n;i++){
if(a[i]!=a[i-1]) s1[i]=a[i],s2[i]=a[i];
else{
s1[i]=*(s3.begin());s3.erase(s1[i]);
set<int>::iterator it=s4.lower_bound(a[i]);
it--;
s2[i]=*it;s4.erase(s2[i]);
}
}
for(vector<int>::iterator it=s1.begin()+1;it!=s1.end();it++)
cout<<*it<<" ";
cout<<endl;
for(vector<int>::iterator it=s2.begin()+1;it!=s2.end();it++)
cout<<*it<<" ";
cout<<endl;
}
return 0;
}
F. Triangular Paths
分析：
其实这题和A，D两题一样，都是找规律的题，但是这道题难度比它们大得多，原因就在于这道题涉及图的知识，需要在图上找规律。
读者可以自行在纸上画一下这张图，大概取到横坐标10左右，会发现这是一个个反斜连通块连在了一起的图。图是一个循环体，接下来就来找规律，我们用ans记录答案。记得初始化为0。我们首先将所有的点按照行从小到大排序，然后按行遍历每个需要经过的位置与它前一个位置比较，通过草拟的图，我们会发现，如果两个位置在同一个连通块的奇数侧花费为0，偶数侧花费为行-列,则ans+=r-c。如果两个位置不在同一连通块，那么我们可以求出他们的行和列的差值，r=r[i]-r[i-1]+1，c=c[i]-c[i-1]+1;那么就可以看作是位置（r,c）和位置(1,1)的情况。这样就很容易分析了。如果它们的位置差奇数个连通块，则ans+=(r[i]-c[i]+1)/2;否则ans+=(r[i]-c[i])/2;
AC代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
struct Edge{
int u,v;
}e[maxn];
int cmp(Edge a,Edge b){
return a.u<b.u;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
ll ans=0;
memset(e,0,sizeof(e));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&e[i].u);
for(int i=1;i<=n;i++) scanf("%d",&e[i].v);
sort(e+1,e+1+n,cmp);
e[0].u=1,e[0].v=1;
for(int i=1;i<=n;i++){
int r1=e[i-1].u,c1=e[i-1].v;
int r2=e[i].u,c2=e[i].v;
if(r2-c2==r1-c1){
if((r2+c2)&1) continue;
else ans+=r2-r1;
}
else{
int r3=r2-r1+1,c3=c2-c1+1;
if((r1+c1)&1) {
ans+=(r3-c3+1)/2;
}
else{
ans+=(r3-c3)/2;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
G. Maximize the Remaining String
蒻蒻写这道题想的有点复杂，没有很快写出来，在后面借鉴了大佬的思路才写出来的。这道题方法很多，但是我觉得最简单也是代码最简洁的思路一定是单调栈。要是读者对单调栈有点生疏，可以去看笔者的另一篇博客，里面有详细介绍和经典例题。
由于该题是一道去重并且让字符串序列最大的题，我们可以先用vis[]数组标记每一个字母，标记的作用是为了让每个字母只能用一次。然后用数组pos[]找到并且记录每一个字母在序列中出现的最后位置,作用是为了在构造单调栈的时候可以特殊化（即不是完全单调，而是在去重基础上的单调）。然后遍历每一个字符，如果当前字符没有被标记并且当前字符大于栈顶字符，并且栈顶字符的最后位置在当前位置之后，那么弹出当前字符，将该字符的标记解除，一直重复到不满足该条件或者栈为空的时候，压入当前元素并标记。最后将栈中的元素逆序输出即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int pos[maxn];
bool vis[30];
int main(){
iostream::sync_with_stdio(false);
int t;cin>>t;
while(t--){
memset(pos,0,sizeof(pos));
for(int i=0;i<28;i++) vis[i]=false;
string str;
cin>>str;
stack<int>s;
for(int i=0;i<str.length();i++) pos[str[i]-'a']=i;
for(int i=0;i<str.length();i++){
if(vis[str[i]-'a']) continue;
while(!s.empty()&&str[i]>str[s.top()]&&i<pos[str[s.top()]-'a']) vis[str[s.top()]-'a']=false,s.pop();
s.push(i);vis[str[i]-'a']=true;
}
vector<char>v;
while(!s.empty()) {v.push_back(str[s.top()]);s.pop();}
for(vector<char>::reverse_iterator it=v.rbegin();it!=v.rend();it++) cout<<*it;
cout<<endl;
}
return 0;
}
|