首页 技术 正文
技术 2022年11月11日
0 收藏 475 点赞 2,434 浏览 3563 个字

contesthunter暑假NOIP模拟赛#1题解:

第一题:杯具大派送

水题。枚举A,B的公约数即可。

#include <algorithm>#include <cmath>#include <iostream>using namespace std;#define MAXN 100010struct node{ int a,b,c;}ans[MAXN];int main() {   int R, G;   scanf("%d%d",&R,&G);   int x=min(R,G);   ,t=MAXN-;   ; i*i<=x; ++i )    {       )        {          &&R%i==)           {ans[s].a=i;            ans[s].b=R/i;            ans[s].c=G/i;            s++;           }           &&R%(x/i)==)           {            ans[t].a=x/i;            ans[t].b=R/(x/i);            ans[t].c=G/(x/i);            t--;           }         }      }   ;i>t;i--)    printf("%d %d %d\n",ans[i].a,ans[i].b,ans[i].c);        printf("%d %d %d\n",ans[i].a,ans[i].b,ans[i].c);   ;}

第二题:另类区间和

动态规划、记忆化搜索

官方题解:

Let f(n, prefix) consider all numbers in the interval [prefix·10n, (prefix+1)·10n>. The function calculates

the total contribution towards the result of n digits yet to be placed to the right of the given prefix.

To calculate f, we add a group of any digit other than the last one in prefix. For example, suppose n=4

and prefix=112. f(4, 112) considers the numbers 1120000 through 1129999. If we decide to append the

group 55 to the number, the contribution of this recursive branch is 52 + f(2, 11255).

It may seem that it takes too many recursive calls to calculate the result. However, many of these yield

the same result for different prefixes, more precisely when the entire interval considered is contained

inside [A, B]. For these cases we can memoize the result (it depends only on n). There are only

O(log B) recursive calls in which we branch without memoization.

#include <algorithm>#include <cstdio>#include <cstring>using namespace std;typedef long long llint;llint A, B;llint p10[16];llint memo[16][11];llint intersect( int n, llint prefix ) {   if( n < 0 ) return 0;   llint lo = max( prefix * p10[n], A );   llint hi = min( (prefix+1) * p10[n] - 1, B );   if( lo > hi ) return 0;   return hi-lo+1;}llint rec( int n, int prev, llint prefix ) {   llint mini = prefix * p10[n];   llint maxi = (prefix+1) * p10[n] - 1;   if( mini > B || maxi < A ) return 0;   if( mini >= A && maxi <= B && memo[n][prev] != -1 ) return memo[n][prev];   llint ret = 0;   for( int digit = 0; digit <= 9; ++digit ) {      if( digit == prev ) continue;      llint t = prefix;      for( int k = 1; k <= n; ++k ) {         t = t*10+digit;         ret += digit * k * k * (intersect( n-k, t )-intersect( n-k-1, t*10+digit)) + rec( n-k, digit, t );      }   }   if( mini >= A && maxi <= B ) memo[n][prev] = ret;   return ret;}int main( void ) {   scanf( "%lld%lld", &A, &B );   p10[0] = 1;   for( int i = 1; i <= 15; ++i ) p10[i] = p10[i-1] * 10;   memset( memo, -1, sizeof memo );   printf( "%lld\n", rec( 15, 10, 0 ) );   return 0;}

第三题:01序列

线段树

交替出现的序列才是合法的序列,题目要求最长序列的长度。我们可以用线段树来解决。

当前区间最长序列长度应该等于下面三者的最大值:

左儿子区间的最长序列、右儿子区间的最长序列、以及

左儿子的后缀与右儿子的前缀组成的序列。

所以每个节点需要保存5个值:区间最长的合法序列的长度,前缀长度,后缀长度,前缀的第一个字符,后缀的最后一个字符。

其他的我们还需要知道前缀的最后一个字符,但我们可以通过前缀长度和前缀的第一个字符推导出来,后缀的第一个字符我们也可以通过后缀的最后字符和后缀长度推导出来。

标程:(01序列)

#include <cstdio>#include <iostream>#include <vector>#include <algorithm>using namespace std;const int mxn = 1<<19;struct node{int mx;int left, right;char start, end;int len;} data[2*mxn];node operator +( const node &a, const node &b ){node ret;ret.start = a.start;ret.end = b.end;ret.len = a.len + b.len;ret.left = a.left;if( a.len == a.left && a.end != b.start ) ret.left += b.left;ret.right = b.right;if( b.len == b.right && a.end != b.start ) ret.right += a.right;ret.mx = max( max( a.mx, b.mx ), max( ret.left, ret.right ) );if( a.end != b.start ) ret.mx = max( ret.mx, a.right+b.left );return ret;}int n;void construct( int i, int lo, int hi ){  if( hi-lo == 1 ){    if( lo >= n ) data[i].mx = data[i].left = data[i].right = 0;    else data[i].mx = data[i].left = data[i].right = 1;    data[i].start = data[i].end = 'L';    data[i].len = 1;    return;  }  construct( 2*i, lo, (lo+hi)/2 );  construct( 2*i+1, (lo+hi)/2, hi );  data[i] = data[2*i] + data[2*i+1];}void change( int i ){  i += mxn;  if( data[i].start == 'L' ) data[i].start = 'R';  else data[i].start = 'L';  data[i].end = data[i].start;  for( i /= 2; i > 0; i /= 2 )    data[i] = data[2*i] + data[2*i+1];}int main(){  int q;  scanf( "%d %d", &n, &q );  construct( 1, 0, mxn );  for( ; q > 0; q-- ){    int i;    scanf( "%d", &i ); i--;    change(i);    printf( "%d\n", data[1].mx );  }  return 0;}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,494
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,907
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,740
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,495
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:8,133
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,297