比赛地址：Codeforces Round #426 (Div. 2)
C. The Meaningless Game
题意：
是两个人比赛，每轮会有一个数字k，一个人乘k分，一个人乘K^2分，现在给你最终的分数，问是否可能。
解法：
假设最终分数为a、b，可以发现只要a*b能开三次方（开三次方为p），并且a%p==0&&b%p==0即可。 可以证明这是充要条件。 必要性： 每次一个人获得ki分，一个人获得ki^2分，那么最后a*b=(k1*k2*…*kn)^3 充分性： 。
代码：
#include<iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main(){
int N;
long long a, b;
cin >> N;
while( N-- ){
scanf(
"%I64d%I64d", &a, &b );
long long temp =
pow( (
double)a * b,
1.0 /
3.0 ) +
0.5;
if( temp * temp * temp == a * b && a % temp ==
0 && b % temp ==
0 ){
puts(
"YES");
}
else{
puts(
"NO");
}
}
return 0;
}
D. The Bakery
非常不错的题目！
题意：
给你一串数字，需要分成k份，每份的价值为该份中不同数字的个数。为怎么分价值最大，求这个最大价值。
思路
这种题肯定是动态规划了，然后发现裸的dp是n方的，所以需要优化。 这时候发现状态基本上只能这么设了，那么只能在转移的是时候优化了，从n到logn最常用的优化就是用线段树。 设状态dp[i][j]表示前j个数分成i份的最大价值。 对于第j个数字，假设它之前第一个和他相等的数字的位置是p，那么那么第j个数字只会对dp[i-1][p]到dp[i-1][j-1]这些状态贡献1。那么我们就用线段树来记录和查询这些贡献。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node{
int l, r, tag, mx;
};
Node node[
35001*
4];
int dp[
55][
35001];
void push_up(
int rt ){
node[rt].mx = max( node[rt*
2].mx, node[rt*
2+
1].mx);
}
void push_down(
int rt){
node[rt*
2].mx += node[rt].tag;
node[rt*
2].tag += node[rt].tag;
node[rt*
2+
1].mx += node[rt].tag;
node[rt*
2+
1].tag += node[rt].tag;
node[rt].tag =
0;
}
void build(
int k,
int rt,
int l,
int r){
if( l == r ){
node[rt] = { l, r,
0, dp[k][l] };
return;
}
node[rt] = { l, r,
0,
0 };
int mid = ( l + r ) /
2;
build( k, rt *
2, l, mid );
build( k, rt *
2 +
1, mid +
1, r );
push_up( rt );
}
void add(
int rt,
int l,
int r,
int val ){
if( l <= node[rt].l && node[rt].r <= r ){
node[rt].mx += val;
node[rt].tag += val;
return;
}
push_down( rt );
int mid = ( node[rt].l + node[rt].r ) /
2;
if( l <= mid ){
add( rt *
2, l, r, val );
}
if( mid +
1 <= r ){
add( rt *
2 +
1, l, r, val );
}
push_up( rt );
}
int query(
int rt,
int l,
int r ){
if( r < l ){
return 0;
}
if( l <= node[rt].l && node[rt].r <= r ){
return node[rt].mx;
}
push_down(rt);
int mid = ( node[rt].l + node[rt].r ) /
2;
int ans =
0;
if( l <= mid ){
ans = max( ans, query( rt *
2, l, r ) );
}
if( mid +
1 <= r ){
ans = max( ans, query( rt *
2 +
1, l, r ) );
}
push_up( rt );
return ans;
}
int num[
35001];
int N, K;
int last[
35001], ed[
35001];
int main(){
memset( last,
0,
sizeof( last ) );
memset( ed,
0,
sizeof( ed ) );
memset( dp,
0,
sizeof( dp ) );
scanf(
"%d%d", &N, &K );
for(
int i =
1; i <= N; i++ ){
scanf(
"%d", &num[i] );
last[i] = ed[num[i]];
ed[num[i]] = i;
}
for(
int i =
1; i <= K; i++ ){
build( i -
1,
1,
0, N );
for(
int j =
1; j <= N; j++ ){
add(
1, last[j], j -
1,
1 );
dp[i][j] = query(
1,
0, j -
1 );
}
}
printf(
"%d\n", dp[K][N] );
return 0;
}
