第一题:可将矩阵看成一维数组a[N*N],进行简单运算即可。(一维转二维公式)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,t;
cin>>n>>t;
t%=(n*n);
int a=t/n+1,b=t%n+1;
cout<<a<<' '<<b;
return 0;
}
第二题:运用结构体,w:所含灵石数量;h:传送所需灵石数量;ca:差。 对h从小到大进行排序,接着i从1到n循环,如果碰到传送所需灵石>此刻现有灵石数量,直接跳出;如果差<0,则视为不利,continue。 最后输出现有灵石数量即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct Node{
int w,h,ca;
}a[N];
bool cmp(Node x,Node y)
{
return x.h<y.h;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&a[i].w,&a[i].h);
a[i].ca=a[i].w-a[i].h;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
{
if(a[i].h>m) break;
if(a[i].ca<=0) continue;
m+=a[i].ca;
}
printf("%d",m);
return 0;
}
第三题:找!规!律! 可发现输出仅有2种:0、1。 若数组和第一次跳跃后排列相同,则直接输出0。 此刻我们会下意识用cnt计数,可尝试几个样例后发现,除0、1之外无他数,可判断如果第一次有不相同的,必定是1,直接return 0。循环结束则表明全部相同,输出0即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int a[N],b[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",a+i);
b[i]=a[i];
}
bool done=true;
for(int i=1;i<=n;++i)
{
for(int j=n;j>=i;--j)
{
if(a[j]>=a[i])
{
if(a[j]!=b[i])
{
puts("1");
return 0;
}
b[i]=a[j];
break;
}
}
}
puts("0");
return 0;
}
第四题:应该是两个dp结束,可我只写出第一个分别求最大经验值的典型背包问题代码,剩下部分尚未完成。 由于无法确定从哪里开始选则,往哪一侧先计算,故不可直接模拟。 AC40%,大家仅供参考!
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
typedef long long ll;
ll a[N],b[N][3],f[N],p[N],r;
ll n,m,t;
int main()
{
scanf("%lld%lld%lld",&n,&m,&t);
for(int k=1;k<=n;++k)
{
scanf("%lld",a+k);
memset(f,0,sizeof f);
for(ll i=1,w,time;i<=a[k];++i)
{
scanf("%lld%lld",&w,&time);
for(int j=t;j>=time;--j)
{
f[j]=max(f[j],f[j-time]+w);
}
}
p[++r]=f[t];
}
//下面代码不正确
//ll mx=0,d1[N],d2[N],u=0,cnt1=0,v=0,cnt2=0;
//for(int i=1;i<=r-m+1;++i)
//{
// u=cnt1=v=cnt2=0;
// for(int j=i;j<i+m;++j)
// {
// u+=p[j];
// cnt1+=u;
// u=cnt1;
// }
// for(int j=i+m-1;j>=i;--j)
// {
// v+=p[j];
// cnt2+=v;
// v=cnt2;
// }
// mx=max(mx,cnt1);
// mx=max(mx,cnt2);
//}
//printf("%lld",mx);
return 0;
}
总结:这一次不算太难,特别第三题,得分很容易。没有出现图论和最小生成树问题。 Goodbye!