QDU第一届程序设计大赛——E到I题解法（非官方题解）
2024-08-23 01:01:46
题目链接https://qduoj.com/contest/28/problems，密码：qdu1230
E题：
思路：先进行排序，然后去暴力模拟就可以，但可能WA了几次，导致此题没解出来，有点可惜
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int a[3005];
int b[3005];
int main()
{
int n,m;
cin>>n>>m;
for(int t=0;t<n;t++)
{
scanf("%d",&a[t]);
}
for(int t=0;t<m;t++)
{
scanf("%d",&b[t]);
}
sort(a,a+n);
sort(b,b+m);
int ma=0,mb=0;
int maxna=0;
int maxnb=0;
for(int t=0;t<n;t++)
{
for(int j=t;j<n;j++)
{
if(ma==5)
{
break;
}
if(a[j]-a[t]<=3)
{
ma++;
}
else
{
ma=0;
break;
}
maxna=max(maxna,ma);
if(j==n-1)
{
ma=0;
}
}
}
for(int t=0;t<m;t++)
{
for(int j=t;j<m;j++)
{
if(mb==5)
{
break;
}
if(b[j]-b[t]<=3)
{
mb++;
}
else
{
mb=0;
break;
}
maxnb=max(maxnb,mb);
if(j==m-1)
{
mb=0;
}
}
}
cout<<maxna<<endl;
cout<<maxnb<<endl;
if(maxna<=maxnb)
{
cout<<"liangliang\\O..o\\"<<endl;
}
else
{
cout<<"gg/o..O/"<<endl;
}
return 0;
}F题：
思路：首先对于题目的理解不能有错误，是进行任意轮的命令判断是否能到达，不是就执行那一轮命令，那我们不妨设进行了k轮，然后把每次的坐标变换记录，判断在k轮是否能到达，k的值为（a-每一次的变化量）/一轮的变换量
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
string str;
struct node
{
int x,y;
}pos[1005];
int main()
{
int a,b;
while(cin>>a>>b>>str)
{
int len=str.length();
int x=0,y=0;
int flag=0;
if(x==a&&y==b)
{
cout<<"Yes"<<endl;
continue;
}
for(int t=0;t<len;t++)
{
if(str[t]=='U')
y++;
if(str[t]=='D')
y--;
if(str[t]=='L')
x--;
if(str[t]=='R')
x++;
pos[t].x=x;
pos[t].y=y;
//cout<<pos[t].x<<" "<<pos[t].y<<endl;
}
int k;
for(int t=0;t<len;t++)
{
if(x)
{
k=(a-pos[t].x)/x;
}
else if(y)
{
k=(b-pos[t].y)/y;
}
if(k<0)
k=0;
if(a==k*x+pos[t].x&&b==k*y+pos[t].y)
{
flag=1;
break;
}
}
if(flag)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 0;
}G题:G题看一下数据量就会明白暴力必然超时，那如何去解，我们可以进行分组枚举所有结果，然后，去另一个查找有多少个相等的。我们可以有1，4和2，3两种分法，我们看1，4也十分容易超时，故选用2，3，然后把所有的结果分别放在两个数组里。我们查找的时候用二分进行查找，故要先进行排序，然后我们在较小的里面找较大的，复杂度稍低，然后我们不应该是找是否存在，而应该找存在多少个，所以一个是找左边的下标，一个找右边的下标，这样一减就是个数。还有一个问题，就是开数组的大小，我一开始开的是1e6和1e4，但是会溢出，我就试着跑了下，一个在1e6+1e4左右，另一个没跑，直接就多开大算了。
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[10400000];
int b[14005];
int k1,k2;
// 查找第一个相等的元素
int findFirstEqual(int a[], int key) {
int left = 0;
int right = k1 - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] >= key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (left < k1 && a[left] == key) {
return left;
}
return -1;
}
// 查找最后一个相等的元素
int findLastEqual(int a[], int key) {
int left = 0;
int right = k1- 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] <= key) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
if (right >= 0 && a[right] == key) {
return right;
}
return -1;
}
int main()
{
int T;
cin>>T;
int x1,x2,x3,x4,x5;
for(int t=0;t<T;t++)
{
k1=0;
k2=0;
scanf("%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5);
for(int j1=-50;j1<=50;j1++)
{
for(int j2=-50;j2<=50;j2++)
{
for(int j3=-50;j3<=50;j3++)
{
if(j1==0||j2==0||j3==0)
{
continue;
}
a[k1++]=x1*j1*j1*j1+x2*j2*j2*j2+x3*j3*j3*j3;
}
}
}
for(int j1=-50;j1<=50;j1++)
{
for(int j2=-50;j2<=50;j2++)
{
if(j1==0||j2==0)
{
continue;
}
b[k2++]=x4*j1*j1*j1+x5*j2*j2*j2;
}
}
sort(a,a+k1);
int sum=0;
for(int j=0;j<k2;j++)
{
int l,r;
if(findFirstEqual(a,-b[j])!=-1&&findLastEqual(a,-b[j])!=-1)
{
l=findFirstEqual(a,-b[j]);
r=findLastEqual(a,-b[j]);
sum+=r-l+1;
}
}
cout<<sum<<endl;
}
return 0;
} H题：是codeforce一道题的简化版，我的想法是去找原来的串，找原来的串可以通过最长的两个，和最短的两个来确定，通过拼接共有八中情况，由于题目说是有唯一存在，所以必然存在一种是两者相同的，这就是原来的串，找到原来的串，由于数据范围比较小，就可以暴力去找前缀和后缀了，标记一下，最后根据标记来判断前缀和后缀
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
string str[305];
string s1[305],s2[305];
int vis[305]={0};
int main()
{
int n;
cin>>n;
for(int t=0;t<2*n-2;t++)
{
cin>>str[t];
}
string len1[2],len_n[2];
int k1=0,k2=0;
for(int t=0;t<2*n-2;t++)
{
if(str[t].length()==1)
{
len1[k1++]=str[t];
}
if(str[t].length()==n-1)
{
len_n[k2++]=str[t];
}
}
string stand;
string sss1[4],sss2[4];
//八种情况
sss1[0]=len1[0]+len_n[0];
sss1[1]=len_n[0]+len1[0];
sss1[2]=len1[1]+len_n[0];
sss1[3]=len_n[0]+len1[1];
sss2[0]=len1[0]+len_n[1];
sss2[1]=len_n[1]+len1[0];
sss2[2]=len1[1]+len_n[1];
sss2[3]=len_n[1]+len1[1];
for(int t=0;t<4;t++)
{
for(int j=0;j<4;j++)
{
if(sss1[t]==sss2[j])
{
stand=sss1[t];
}
}
}
// cout<<stand<<endl;
string s[205];
s[0]=stand[0];
for(int t=1;t<n-1;t++)
{
s[t]=s[t-1]+stand[t];
}
for(int t=0;t<2*n-2;t++)
{
for(int j=0;j<n-1;j++)
{
if(str[t]==s[j])
{
vis[t]=1;
}
}
}
for(int t=0;t<2*n-2;t++)
{
if(vis[t]==1)
{
cout<<"P";
}
else
{
cout<<"S";
}
}
cout<<endl;
return 0;
}I题：
思路：狼和草是可以共存的群体，羊和狼草都不能共存，我们就可以分为两大阵营，羊，狼草，然后他们的存在状态总的有两种，一在岸上，一种是在船上，当小的等于d时，如果两大阵营的大的超过船的两倍载重，就会出现混的情况，就会混乱，故当小的等于d时，多的必须小于等于2*d，当小的小于d是时，可以不断的去运多的，就不必考虑多的数量，都可以运
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int a,b,c,d;
while(cin>>a>>b>>c>>d)
{
int maxn=max(a+c,b);
int minn=min(a+c,b);
if(minn==d&&maxn<=2*d||(minn<d))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}最新文章
- [知识点]字符串Hash
- 如何计算oracle数据库内存
- 分享一组Rpg Marker人物行走,游戏素材图片，共20张图片
- Golang全接触
- RAW模板命名规范
- oracle 12c 学习系列(1)–12c初体验
- php设计模式七 ---组合模式
- Round #3
- Django常见问题集
- MT【57】2017联赛一试解答倒数第二题:一道不等式的最值
- jQuery跨域调用Web API
- AngularJS入门基础——控制器
- Java编程的逻辑 (55) - 容器类总结
- spacemacs怎样配置编辑器显示行号？
- Python之使用PIL实现cv2
- Java核心编程快速学习(转载)
- OutLook中添加Exchange失败问题
- js中几种常见的方法的实例 shift,unshift,push,prop
- tomcat修改域名和访问域名时去掉项目名
- 理解HBase