首页 > 代码库 > 0904解题报告

0904解题报告

2024-08-12 00:23:05   220人阅读

 第一题

简单模拟，把s拆成二进制形式，然后统计有多少个一，将  ans/n*m   化简即可。

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 long long n,m,s,ans;10 inline long long read()11 {12     long long x=0,f=1;  char ch=getchar();13     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}14     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}15     return x*f;16 }17 long long gcd(long long a,long long b)  {return b==0?a:gcd(b,a%b);}18 int main()19 {20     freopen("huajitree.in","r",stdin);21     freopen("huajitree.out","w",stdout);22     n=read();  m=read();  s=read();23     while(s)  {if(s%2==1)  ans++;  s/=2;}24     long long r=gcd(ans,n*m);25     if(!ans)  printf("0\n");26     else printf("%I64d/%I64d\n",ans/r,m*n/r);27     return 0;28 }
View Code

 第二题

无力吐槽贪心水过，请看正解动态规划。

用sumv和sumh分别维护v和h的前缀和，f[i]表示将前i件物品放入背包的最小代价，那么很容易写出状态转移方程：f[i]=min{f[i],f[j]+sumh[i]*(sumv[i]-sumv[j])}

O（n^2）的时间复杂度，可以过掉60分，然后需要进行斜率优化。

假设从k转移到i比j更优，则有f[k]+sumh[i]*sumv[i]-sumh[i]*sumv[k]<f[j]+sumh[i]*sumv[i]-sumh[i]*sumv[j]

化简得(f[k]-f[j])/(sumv[k]-sumv[j])<sumh[i]

这就是斜率表达式了，然后维护凸包即可。

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 #define MAXN 1000010 9 using namespace std;10 long long n,f[MAXN],v[MAXN],h[MAXN],sumv[MAXN],sumh[MAXN],q[MAXN];11 inline long long read()12 {13     long long x=0,f=1;  char ch=getchar();14     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}15     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}16     return x*f;17 }18 long long slop(long long a,long long b){return (f[a]-f[b])/(sumv[a]-sumv[b]);}19 int main()20 {21     freopen("pack.in","r",stdin);22     freopen("pack.out","w",stdout);23     n=read();24     for(int i=1;i<=n;i++)  25     {26         v[i]=read();  27         h[i]=read();28         sumv[i]=v[i]+sumv[i-1];29         sumh[i]=h[i]+sumh[i-1];30         f[i]=sumv[i]*sumh[i];31     }32     f[1]=v[1]*h[1];  33     long long l=0,r=0;34     for(int i=1;i<=n;i++)35     {36         while(l<r&&slop(q[l],q[l+1])<sumh[i])l++;37         long long t=q[l];38         f[i]=f[t]+sumh[i]*(sumv[i]-sumv[t]);39         while(l<r&&slop(q[r-1],q[r])>slop(q[r],i))r--;40         q[++r]=i;41     }42     printf("%I64d\n",f[n]);43     return 0;44 }
View Code

第三题

线段树维护图的连通性，考试时完全没有想到，写了一个暴力，然后挂了。

0904解题报告


联系
我们