ICPC Arab Collegiate Programming Contest 2013（部分题解）
程序员文章站
2022-07-03 17:50:31
ICPC Arab Collegiate Programming Contest 2013E. Balloons Colors思路：判断第一个数是否等于x最后一个数是否等于y，依次输出即可code：#include#includeusing namespace std;int a[110];int n,x,y;int main(){int t;cin>>t;while(t--){......
7月23日
目录
ICPC Arab Collegiate Programming Contest 2013
ICPC Arab Collegiate Programming Contest 2013
E. Balloons Colors
思路：判断第一个数是否等于x 最后一个数是否等于y，依次输出即可
code：
#include<iostream>
#include<cstdio>
using namespace std;
int a[110];
int n,x,y;
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>x>>y;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(a[1]==x&&a[n]==y) cout<<"BOTH"<<endl;
else if(a[1]==x&&a[n]!=y) cout<<"EASY"<<endl;
else if(a[1]!=x&&a[n]==y) cout<<"HARD"<<endl;
else cout<<"OKAY"<<endl;
}
return 0;
}
F. NASSA's Robot
思路：将？改为全为‘U’ 'D' 'R' 'L'四种情况分别对应最上最下最右最左
code：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false );
cin.tie(0),cout.tie(0);
int t;
cin>>t;
string s;
while(t--){
cin>>s;
int x=0,y=0;
int num=0;
for(int i=0;i<s.size();i++){
if(s[i]=='R') x++;
if(s[i]=='L') x--;
if(s[i]=='U') y++;
if(s[i]=='D') y--;
if(s[i]=='?') num++;
}
int x1=x,y1=y;
int x2=x,y2=y;
while(num--){
x1--;
y1--;
x2++;
y2++;
}
cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
}
return 0;
}
G. The Stones Game
思路：这个题是比较有意思的，总结一下就是指定的玩家总是最后一个移除石头，那么就输出YES 否则NO即 判断n%m==x%m
code：
#include<iostream>
using namespace std;;
int n,m,x;
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>m>>x;
if(n%m==x%m) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
I. Omar Loves Candies
思路：二维前缀和，因为右边的总是比左边的大，下面的也是总比上面的大，所以可以确定子矩阵的右下角（n，m）然后枚举左下角更新最大值
code：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1100;
ll a[N][N];
int n,m;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
cin>>n>>m;
int x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
ll ans=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ans=max(ans,a[n][m]-a[n][j-1]-a[i-1][m]+a[i-1][j-1]);
}
cout<<ans<<endl;
}
return 0;
}
A. The Alphabet Sticker
思路：
去掉首尾的？枚举左右字母中间的？求得？的数量为num，如果左右的字母相同则答案乘1，否则答案乘（num+1）最后输出答案
code：
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int main()
{
std::ios::sync_with_stdio(false );
cin.tie(0),cout.tie(0);
int t;
string s;
cin>>t;
while(t--){
ll ans=1;
cin>>s;
ll num;
int bn=0,ed=0;
for(int i=0;i<s.size();i++){
if(s[i]=='?') continue;
else{
bn=i;
break;
}
}
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='?') continue;
else{
ed=i;
break;
}
}
// cout<<s[bn]<<" "<<s[ed]<<endl;
char l,r;
for(int i=bn;i<=ed;i++){
if(s[i]=='?') num++;
else num=0;
if(s[i]=='?'&&s[i-1]!='?'){
l=s[i-1];
}
if(s[i]=='?'&&s[i+1]!='?'){
r=s[i+1];
if(l==r) ans=ans*1;
else ans=ans*(num+1)%mod;
}
}
cout<<ans<<endl;
}
return 0;
}
L. Omar's Bug
思路：你要知道这个代码自身错哪了，这个是返回第一个大于x的数，如果y==1 的话我们要输出一个正确的答案，那么答案数组里面不可能包含这个数x，从1开始输出，如果y==2 的话 我们的答案数组中必须包括这个数x才能返回一个错误的答案，相应的输出即可
code：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int t;
cin>>t;
int n,x,y;
while(t--){
cin>>n>>x>>y;
if(y==1){
int num=0;
for(int i=1;i<=100;i++){
if(num==n) break;
else if(i!=x){
cout<<i<<" ";
num++;
}
}
cout<<endl;
}
else{
if(x>n){
n--;
int num=1;
while(n--){
cout<<num<<" ";
num++;
}
cout<<x<<endl;
}
else{
int num=1;
while(n--){
cout<<num<<" ";
num++;
}
cout<<endl;
}
}
}
return 0;
}
J. Modified LCS
思路：按照等差数列的公式 f1+d1x=f2+d2y 其中x属于[0,n1-1] y的范围是[0,n2-1] 即为 f2-f1=d1x-d2y 问题就可以转化为满足条件的解 的个数，是不是可以想到扩展欧几里得这个算法，其实这个题就是扩展欧几里得的模板题，建议看下相关的知识点，不然这个题是没法解决的
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll n1,f1,d1,n2,f2,d2;
ll x,y;
ll exgcd(ll a,ll b){//这个就是板子，在上面的连接处给予了相关的证明
if(b==0){
x=1;
y=0;
return a;
}
ll r=exgcd(b,a%b);
ll temp=x;
x=y;
y=temp-(a/b)*y;
return r;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
ll ans;
scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2);
ll f=f2-f1;
ll GCD=exgcd(d1,-d2);
if(f%GCD){//不为0就没有解
cout<<0<<endl;
}
else{
x=x*f/GCD;//求解ax+by=m的一个特解
y=y*f/GCD;
GCD=abs(GCD);
int a=d2/GCD,b=d1/GCD;//最小公倍数就是最小的间隔
while(x<0||y<0) x+=a,y+=b;
while(x>=0&&y>=0) x-=a,y-=b;
if(x<0||y<0) x+=a,y+=b;
ans=min((n1-1-x)/a+1,(n2-1-y)/b+1);//给的x，y的范围内有多少个间隔，取最小的即可
cout<<ans<<endl;
}
}
}
本文地址：https://blog.csdn.net/qq_44797733/article/details/107518756