解题报告
期望
T1 期望得分 100 实际得分 100
T2期望得分 100 实际得分40
T3期望得分 50 实际得分 0
T1 backpack
多重背包板子题
(nleq 1000) 很显然，是不需要任何优化的，同时最下面写了一个二进制优化
/*
by : Zmonarch
知识点 ：
1000不需要用二进制和单调队列优化
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
#define inf 2147483647
#define qwq register
const int kmaxn = 2e3 + 20 ;
const int kmod = 998244353 ;
namespace Base
{
inline int Min(int a , int b) {return a < b ? a : b ;}
inline int Max(int a , int b) {return a < b ? b : a ;}
inline int gcd(int a , int b) {return !b ? a : gcd(b , a % b) ;}
inline int Abs(int a ) {return a < 0 ? - a : a ;}
}
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , m ;
int v[kmaxn] , w[kmaxn] , c[kmaxn] , f[kmaxn][kmaxn] ;
signed main()
{
freopen("backpack.in" , "r" , stdin) ;
freopen("backpack.out" , "w" , stdout) ;
n = read() , m = read() ;
for(qwq int i = 1 ; i <= n ; i++)
v[i] = read() , w[i] = read() , c[i] = read() ;
for(qwq int i = 1 ; i <= n ; i++)
{
for(qwq int j = 0 ; j <= m ; j++)
{
for(qwq int k = 0 ; k <= c[i] ; k++)
{
if(k * v[i] <= j)
{
f[i][j] = Base::Max(f[i - 1][j - k * v[i]] + k * w[i] , f[i][j] );
}
}
}
}
printf("%I64d
" , f[n][m]) ;
return 0 ;
}
/*
int total=1;
for(qwq int i=1;i<=n;i++)
{
for(qwq int j=1;j<=c[i];j<<=1)
{
a[total]=j*w[i];
b[total++]=j*v[i];
c[i]-=j;
}
if(c[i])
{
a[total]=c[i]*w[i];
b[total++]=c[i]*v[i];
}
}
for(qwq int i=1;i<=total;i++)//转化成01背包
{
for(qwq int j=m;j>=b[i];j--)
{
f[j]=max(f[j],f[j-b[i]]+a[i]);
}
}
*//*
by : Zmonarch
知识点 ：
1000不需要用二进制和单调队列优化
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
#define inf 2147483647
#define qwq register
const int kmaxn = 2e3 + 20 ;
const int kmod = 998244353 ;
namespace Base
{
inline int Min(int a , int b) {return a < b ? a : b ;}
inline int Max(int a , int b) {return a < b ? b : a ;}
inline int gcd(int a , int b) {return !b ? a : gcd(b , a % b) ;}
inline int Abs(int a ) {return a < 0 ? - a : a ;}
}
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , m ;
int v[kmaxn] , w[kmaxn] , c[kmaxn] , f[kmaxn][kmaxn] ;
signed main()
{
freopen("backpack.in" , "r" , stdin) ;
freopen("backpack.out" , "w" , stdout) ;
n = read() , m = read() ;
for(qwq int i = 1 ; i <= n ; i++)
v[i] = read() , w[i] = read() , c[i] = read() ;
for(qwq int i = 1 ; i <= n ; i++)
{
for(qwq int j = 0 ; j <= m ; j++)
{
for(qwq int k = 0 ; k <= c[i] ; k++)
{
if(k * v[i] <= j)
{
f[i][j] = Base::Max(f[i - 1][j - k * v[i]] + k * w[i] , f[i][j] );
}
}
}
}
printf("%I64d
" , f[n][m]) ;
return 0 ;
}
/*
int total=1;
for(qwq int i=1;i<=n;i++)
{
for(qwq int j=1;j<=c[i];j<<=1)
{
a[total]=j*w[i];
b[total++]=j*v[i];
c[i]-=j;
}
if(c[i])
{
a[total]=c[i]*w[i];
b[total++]=c[i]*v[i];
}
}
for(qwq int i=1;i<=total;i++)//转化成01背包
{
for(qwq int j=m;j>=b[i];j--)
{
f[j]=max(f[j],f[j-b[i]]+a[i]);
}
}
*/
T2 circulate
给定 (x,y,l,r) 四个数字,并形成一个序列 (x , x+1,x+2…y-1 , y) 的一个序列 ,输出 (l o r) 的区间和。
(x-y leq 10^6 , l ,r leq 10 ^9)
solution
首先看到区间和 , 首先我就想到了线段树 ，然后我们发现 (s) 的长度很小，那么我们就对 (s) 建立线段树，然后我们对区间进行划分，我们找出 (l) 在 (s) 上的投影，然后求区间 (l o s.len) 的和，预计复杂度 (O(frac{(l+r)}{len_s} + log l + log r + len_s imes log len))
应该炸不了，结果 (T) 了，然后我们直接转化一成循环节来搞一下，然后类比分块来搞一下。就 (OK) 了
/*
by : Zmonarch
知识点 ：
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 998244353 ;
namespace Base
{
inline int Min(int a , int b) {return a < b ? a : b ;}
inline int Max(int a , int b) {return a < b ? b : a ;}
inline int gcd(int a , int b) {return !b ? a : gcd(b , a % b) ;}
inline int Abs(int a ) {return a < 0 ? - a : a ;}
}
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int x , y , L , R , cnt , ss ;
int num[kmaxn] , cover[kmaxn] , sum[kmaxn];
signed main()
{
x = read() , y = read() , L = read() , R = read() ;
if(x < y) std::swap(x , y) ;
for(int i = x ; i <= y ; i++)
{
int k = i , s = 0 ;
while(k)
{
cover[++s] = k % 10 ;
k /= 10 ;
}
for(int j = s ; j >= 1 ; j--)
num[++cnt] = cover[j] ;
}
for(int i = 1 ; i <= cnt ; i++) sum[i] = sum[i - 1] + num[i] ;
int lenr = R / cnt , lenl = L / cnt ;
int r = R % cnt ; if(r == 0) r = cnt ;
int l = L % cnt ; if(l == 0) l = cnt ;
printf("%lld
" , (lenr - lenl - 1 ) * sum[cnt] + sum[cnt] - sum[l - 1] + sum[r] ) ;
return 0 ;
}
T3 merge
【description】
(Cindy) 和 (Dan) 在玩一个游戏。
一开始 (Cindy) 想出了 (N) 个数，接着她把这 (N) 个数全部给了 (Dan) 。
(Dan) 得到这组数后，它会挑出 (3) 个数（如果不足 (3) 个则全部挑出）。(Dan) 会把这几个数加起来变成一个数，然后再把这个数与剩下的数再放到一起。(Dan) 会一直这样做，直到最后只剩下一个数。
(Cindy) 则会在旁边记下每次 (Dan) 得到的数，她把这些数加起来，作为本次游戏的得分。她想知道，对于一组数，(Dan) 能得到的最大的得分是多少？
数据 (nleq 10^6)
【solution】:
有一个结论，就是最大得分就是最大数不断去运算。没有什么证明，既然得分最大，我们令最大的数进行运算的次数最多，然后就OK了，我当时看错题目了。
/*
by : Zmonarch
知识点 ：
对于 50% 的数据，是可以搜索做的
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
#define inf 2147483647
const int kmaxn = 1e3 + 10 ;
const int kmod = 998244353 ;
namespace Base
{
inline int Min(int a , int b) {return a < b ? a : b ;}
inline int Max(int a , int b) {return a < b ? b : a ;}
inline int gcd(int a , int b) {return !b ? a : gcd(b , a % b) ;}
inline int Abs(int a ) {return a < 0 ? - a : a ;}
}
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , num[kmaxn] , ret ;
std::priority_queue<int> q ;
signed main()
{
n = read() ;
for(int i = 1 ; i <= n ; i++) q.push(read());
int ret = 0 , num = 0;
if(n <= 3)
{
while(!q.empty())
{
ret += q.top() ;
q.pop() ;
}
printf("%lld
" , ret) ;
return 0;
}
while(q.size() != 1)
{
int tmp = 0 , sum = 0 ;
while(!q.empty())
{
sum += q.top() ;
q.pop() ;
tmp++ ;
if(tmp == 3) break ;
}
ret += sum ;
q.push(sum) ;
}
printf("%lld
" , ret) ;
return 0 ;
}
经验：
- (1.) 首先先拿出 (30) 分钟读题，读错题非常亏
- (2.) 先不要质疑自己推出来的结论。