【题目传送门】http://7xjob4.com1.z0.glb.clouddn.com/30a7f1a788b43f34819586f3593d670a
【Problem A. Adjustment Office 】
【题意】 给了一个N*N的矩阵，矩阵中每个坐标为x,y的格子的值为x+y。有Q个询问，询问一行或者一列的和，然后清空这一行或者一列。
【解题方法】脑洞题。由于每次都要清空，所以一个点的权值只会被加一次，并且权值的分布相当有规律。所以只需要统计一下那些行哪些列被访问过了。以后询问的时候，先加上所有的权值，再减去哪些被询问过的位置的权值，总的复杂度是O(q)的。
【AC 代码】
#include<bits/stdc++.h>
using namespace std;
const int N =2e6;
#define LL long long
LL c,r,numc,numr;
int flagc[N],flagr[N];
int main()
{
freopen("adjustment.in","r",stdin);
freopen("adjustment.out","w",stdout);
int n,q,t;
char s[5];
scanf("%d%d",&n,&q);
for(int i=0;i<q;i++){
scanf("%s%d",s,&t);
if(s[0]=='R'){
if(flagr[t]==0) {
printf("%I64d\n",1ll*(2*t+1+n)*n/2-numc*t-c);
numr++;
r+=t;
flagr[t]=1;
}
else printf("0\n");
}
else{
if(flagc[t]==0){
printf("%I64d\n",1ll*(2*t+1+n)*n/2-numr*t-r);
numc++;
c+=t;
flagc[t]=1;
}
else printf("0\n");
}
}
return 0;
}【Problem E. Easy Problemset】
【题意】难得解释，看题了。
【解题方法】水题，简单模拟一下就可以了。
【AC 代码】
//
//HDU 4417
//Created by just_sort 2016/8/22
//All Rights Reserved
//
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[12][12];
int b[200];
int main()
{
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
scanf("%d%d",&n,&k);
int x[12];
int cnt=1,maxx=-1;
for(int i=1; i<=n; i++){
scanf("%d",&x[i]);
maxx=max(maxx,x[i]);
for(int j=1; j<=x[i]; j++){
scanf("%d",&a[i][j]);
}
}
memset(b,0,sizeof(b));
int j=1;
for(int i=1; i<=maxx; i++){
while(j<=n){
if(i<=x[j])
b[cnt++]=a[j][i];
else b[cnt++]=50;
j++;
}
j=1;
}
//for(int i=1; i<cnt; i++) printf("%d ",b[i]);puts("");
int step=0,ans=0;
for(int i=1; i<cnt; i++)
{
if(b[i]>=ans){
ans+=b[i];
step++;
if(step==k) break;
}
}
//cout<<ans<<endl;
ans=ans+(k-step)*50;
printf("%d\n",ans);
return 0;
}【Problem F. Froggy Ford】
【题意】青蛙过河，河中有若干个石头，现在你可以加一个石头，使得青蛙从左岸跳到右岸的最大跳跃距离最小。
【解题方法】把左岸和右岸作为两个虚节点，用kruskal的思路处理出每个点到左岸需要跳跃的最大距离st[i]（最优情况下）和每个点到右岸的最大距离ed[i]，然后枚举两个点，在这两个点的中点放一个石头，得到ma=max(st[i],ed[j],dis(i,j)/2)，如果这个值比答案更优，就更新答案，同时记录新放的石头的坐标。
【AC 代码】
//
//F Froggy Ford
//Created by just_sort 2016/8/24
//All rights Reserved
//
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1005;
double g[maxn][maxn];
double w;
bool vis[maxn];
int px[maxn],py[maxn];
int getdis(int i,int j)
{
return sqrt(double((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j])));
}
void zxPrim1(int n,double dis[])
{
for(int i=1; i<=n; i++) dis[i] = px[i];
memset(vis,0,sizeof(vis));
for(int i=1; i<n; i++)
{
double minn=1e18;
int mark = 0;
for(int j=1; j<=n; j++) if(!vis[j]&&dis[j]<minn){mark=j; minn=dis[j];}
if(!mark) break;
vis[mark]=1;
for(int j=1; j<=n; j++)
if(!vis[j]&&dis[j]>max(minn,1.0*g[mark][j])) dis[j] = max(minn,1.0*g[mark][j]);
}
}
void fxPrim2(int n,double dis[])
{
for(int i=1; i<=n; i++) dis[i] = (w-px[i])*1.0;
memset(vis,0,sizeof(vis));
for(int i=1; i<n; i++)
{
double minn=1e18;
int mark=0;
for(int j=1; j<=n; j++) if(!vis[j]&&dis[j]<minn) {mark=j;minn=dis[j];};
if(!mark) break;
vis[mark] = 1;
for(int j=1; j<=n; j++)
if(!vis[j]&&dis[j]>max(minn,1.0*g[mark][j])) dis[j] = max(minn,1.0*g[mark][j]);
}
}
double dis1[maxn],dis2[maxn];
int main()
{
int n;
scanf("%lf%d",&w,&n);
for(int i=1; i<=n; i++) scanf("%d%d",&px[i],&py[i]);
for(int i=1; i<=n; i++){
for(int j=1; j<i; j++){
g[i][j]=g[j][i]=getdis(i,j);
}
}
zxPrim1(n,dis1);
fxPrim2(n,dis2);
double ans = 1e18;
double ansx = w/2.0,ansy = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(i!=j)
{
double temp = max(dis1[i],max(dis2[j],g[i][j]/2));
if(ans>temp)
{
ans = temp;
ansx = 1.0*(px[i]+px[j])/2.0;
ansy = 1.0*(py[i]+py[j])/2.0;
}
}
}
}
for(int i=1; i<=n; i++)
{
double temp = max(px[i]/2.0,dis2[i]);
if(ans>temp)
{
ans = temp;
ansx = 1.0*px[i]/2.0;
ansy = 1.0*py[i];
}
temp = max((w-px[i])/2.0,dis1[i]);
if(ans>temp)
{
ans = temp;
ansx = 1.0*(px[i]+w)/2.0;
ansy = 1.0*py[i];
}
}
printf("%.3f %.3f\n",ansx,ansy);
return 0;
}
【Problem G. Generators】
【题意】给n个序列和一个数k,但是这里n个数的序列式通过x[i]=(x0*a+b)%c确定下来的，然后从这n个序列里面分别选择1个数，使得这n个数的和对k取余不等于0。求最大的和。
【解体方法】容易想到在不超过c次的操作后，每个序列将出现循环，因此我们完全可以保存每个序列的信息，但是我们这里在生成的序列的过程中，直接保存每个序列里面的最大值和次大值得信息。然后得到了最大值的和，如果膜上k不等于0的话，就直接输出答案，否则分别用每个序列的次大值替换相应的最大值，维护最大的答案。注意判断无解，还有记录位置信息。
【AC 代码】
#include<cstdio>
#include<cstring>
using namespace std;
const int N =11000;
#define LL long long
struct node
{
int id,x,mod;
} dp[N][2];
int flag[1100];
int main()
{
freopen("generators.in","r",stdin);
freopen("generators.out","w",stdout);
int n,x0,a,b,c;
LL k;
scanf("%d%I64d",&n,&k);
for(int i=0; i<n; i++)
{
dp[i][0].x=-1;
dp[i][1].x=-1;
dp[i][0].mod=-1;
dp[i][1].mod=-1;
}
for(int i=0; i<n; i++)
{
memset(flag,0,sizeof(flag));
scanf("%d%d%d%d",&x0,&a,&b,&c);
int t=x0,cnt=0;
while(flag[t]==0)
{
flag[t]=1;
if(t>dp[i][0].x)
{
if(dp[i][0].x==-1)
{
dp[i][0]= {cnt,t,(int)((1ll*t)%k)};
}
else if(dp[i][0].mod==(int)((1ll*t)%k))
{
dp[i][0]= {cnt,t,(int)((1ll*t)%k)};
}
else
{
dp[i][1]=dp[i][0];
dp[i][0]= {cnt,t,(int)((1ll*t)%k)};
}
}
else if(dp[i][1].x<t)
{
if((int)((1ll*t)%k)!=dp[i][0].mod) dp[i][1]= {cnt,t,(int)((1ll*t)%k)};
}
cnt++;
t=(t*a+b)%c;
}
}
/*for(int i=0;i<n;i++){
printf("%d %d %d",dp[i][0].id,dp[i][0].x,dp[i][0].mod);
printf(" %d %d %d\n",dp[i][1].id,dp[i][1].x,dp[i][1].mod);
}*/
LL sum=0;
for(int i=0; i<n; i++)
{
sum+=dp[i][0].x;
}
if(sum%k!=0)
{
printf("%I64d\n",sum);
for(int i=0; i<n; i++)
{
printf("%d ",dp[i][0].id);
}
return 0;
}
LL ans=-1;
int ff=-1;
for(int i=0; i<n; i++)
{
if(dp[i][1].x==-1) continue;
else
{
if(ans<sum-dp[i][0].x+dp[i][1].x)
{
ans=sum-dp[i][0].x+dp[i][1].x;
ff=i;
}
}
}
if(ans==-1) printf("-1\n");
else
{
printf("%I64d\n",ans);
for(int i=0; i<n; i++)
{
if(ff==i) printf("%d ",dp[i][1].id);
else printf("%d ",dp[i][0].id);
}
}
return 0;
}
京公网安备 11010502036488号