未完待續...

• T1：牛牛的方程式
• • title
  • solution
  • code
• T2：牛牛的猜數游戲
• • title
  • solution
  • code
• T3：牛牛的湊數游戲
• • title
  • solution
  • code

T1：牛牛的方程式

title

solution

因為浮點錯誤炸了70pts

這個三元一次不定方程呢，其實也沒有特別難
只需要在二元一次不定方程$Ax+By=C$上面略作變化即可！

將其轉化為二元一次不定方程，假設$c，z$為已知量
$$ax+by+cz=d\dots \dots ①$$$$ax+by=d?cz\dots \dots ②$$
此時可以直接套用$exgcd$解出$Ax+By=1\dots \dots ③$的特殊值$x,y$
我們知道$exgcd$的有解要保證$gcd(A,B)|C$
即對于方程②而言，要求$gcd(a,b)|(d?cz)$
那么我們可以巧妙通過這一個限制，來檢驗$z$是否為整數
在代碼中就是一句$if$判斷

if( ( d - c ) % gcd( a, b ) == 0 ) YES;

但是！！！
別忘記，$a,b,c,d,x,y,z$都可以是$0$

就是這個$0$的原因，導致了爺的浮點錯誤

所以，賽后，化身諸葛亮，直接$if?else$選擇結構大師上線
①：$d=0$，此時$x=y=z=0$是一組解，$YES$
②：$d=0,a=b=c=0$，$x,y,z$無解，$NO$
③：$a,b,c$有且只有一個為$0$，假設為$T$，則直接判斷$T|d$
能整除，$YES$，否則，$NO$
④：$a,b,c$有且只有兩個為$0$，假設為$S,T$
該情況即為一般形式的$Ax+By=C$，$exgcd$直接搞就van事
⑤：$a\times b\times c=0$
這個情況什么意思呢？就是在上面三元一次轉二元一次最后判斷$z$是否有解的時候
$z$可能等于$0$，那么就需要滿足$gcd(a,b)|d$即可

具體詳見代碼——

code

#include <cstdio> #include <iostream> using namespace std; #define ll long longvoid exgcd( ll a, ll b, ll &d, ll &x, ll &y ) {if( ! b ) d = a, x = 1, y = 0;else {exgcd( b, a % b, d, y, x );y -= x * ( a / b );} }int main() {int T;ll a, b, c, d;scanf( "%d", &T );while( T -- ) {scanf( "%lld %lld %lld %lld", &a, &b, &c, &d );if( ! d ) {printf( "YES\n" );continue;}if( ! a && ! b && ! c ) {printf( "NO\n" );continue;}if( ! a && ! b ) {if( d % c ) printf( "NO\n" );else printf( "YES\n" );continue;}if( ! a && ! c ) {if( d % b ) printf( "NO\n" );else printf( "YES\n" );continue;}if( ! b && ! c ) {if( d % a ) printf( "NO\n" );else printf( "YES\n" );continue;}bool flag = 1;ll gcd, x, y;exgcd( max( a, b ), min( a, b ), gcd, x, y );if( a && b && ( d % gcd == 0 || ( d - c ) % gcd == 0 ) ) flag = 0;exgcd( max( a, c ), min( a, c ), gcd, x, y );if( a && c && ( d % gcd == 0 || ( d - b ) % gcd == 0 ) ) flag = 0;exgcd( max( b, c ), min( b, c ), gcd, x, y );if( b && c && ( d % gcd == 0 || ( d - a ) % gcd == 0 ) ) flag = 0;if( ! flag ) printf( "YES\n" );else printf( "NO\n" );}return 0; }

T2：牛牛的猜數游戲

title

solution

這道題剛開始做的時候，真的沒想到怎么做，就敲了個暴力30pts，后兩道做不動的時候，又跑回來康康，這一瞅不得了，直接干翻這道題

分享一下我的心路歷程吧
看到一個區間$[l,r]$的時候，腦海里常見的套路就應該出來
·線段樹、樹狀數組
·差分$S(r)?S(l?1)$，時常伴隨著從小到大排序操作

此題也不例外，我第一眼就往差分上面靠
企圖通過$S(r)?S(l?1)$再排序搭配樹狀數組，線性求解
用$map，hash$保存杯子的排列

但是不出十秒，我就把自己扼殺在搖籃里了
因為這個杯子之間的排列似乎不支持減法直接求解

此時最明智的方法——暴力跑路

過了一個小時后，回來，就突然——心靈感應吧，我就覺得這道題在誘惑未成年犯罪
題面全身上下都充斥了——“我很簡單，快來做我”

我一直沒有放下差分的想法，我認為差分是肯定可以的！

于是，我開始手玩一波數據，$l?1$，$r$的杯子排列方式進行對比

驚奇發現，這個差分似乎可以從下標方面入手！！我不應該執著于具體的球不放
假設操作到$l?1$后的情況：$1,5,3,2,4$
然后操作到$r$后的情況：$2,3,4,5,1$
看似沒啥關聯，實則暗藏玄機——拋開對實際的球的執念
發現對于$l?1$的第一個位置的球不管是不是$1$，在$r$的時候都會出現在最后一個位置上！！
所以！！只需要線性跑$[1,i]$操作后的球的排列
然后對于每一次查詢$[l,r]$，就去找$l?1,r$之間的對應關系，將其應用在最初始的有序排列上
不就剛好相當于把$[1,l?1]$之間的交換操作影響去掉了嗎

code

#include <cstdio> #include <iostream> using namespace std; #define MAXN 100005 struct node {int l, r; }opt[MAXN], query[MAXN]; int n, m, cnt; int base[15], p[15]; int f[MAXN][15];int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ )scanf( "%d %d", &opt[i].l, &opt[i].r );for( int i = 1, l, r;i <= m;i ++ )scanf( "%d %d", &query[i].l, &query[i].r );for( int i = 0;i <= 9;i ++ )f[0][i] = base[i] = i;for( int i = 1;i <= n;i ++ ) {swap( base[opt[i].l], base[opt[i].r] );for( int j = 0;j <= 9;j ++ )f[i][j] = base[j];}for( int i = 1;i <= m;i ++ ) {int l = query[i].l, r = query[i].r;for( int j = 0;j <= 9;j ++ )for( int k = 0;k <= 9;k ++ )if( f[l - 1][j] == f[r][k] ) {p[k] = j;break;}for( int j = 0;j < 9;j ++ )printf( "%d ", p[j] );printf( "%d\n", p[9] );}return 0; }

T3：牛牛的湊數游戲

title

solution

一. 首先10pts的暴力，肯定是基本功過硬，前綴和能拿到
暴力yyds！！

二. 比賽時，我對【輸入的$a_i$?為$2$的非負整數冪】這個暴力分有很大的想法
因為每個數都有對應的二進制，意思就是如果$2$的每一個冪都被包含在區間里的話，每兩個冪之間的數都可以被湊出來
但是我發現自己的時間復雜度$O(n^{2}logn)$

牛客的出題人真的蠻良心的了，這兩個部分分的思路組合起來，差不多就是正解那個方向了

通過第一個暴力的前綴和可得
$[1,i]$的$a$值和$+1$如果小于$a_{i+1}$，那么$({\sum }_{i=1}^i{a}_i)+1$肯定是湊不出來的

所以我們進行以下操作
假設上一個可能答案是$last$，且小于等于$last$的所有數都能被湊出來
求和所有$a[i]\le last$，記為$S$
下一個可能答案$sum=last+1$，求和所有$a[i]\le sum$，記為$T$
如果$S=T$，則表明$sum$無法被湊出來
每一次都把$T$置為上一次的答案$last=T,sum=last+1$
發現$sum$的取值是不斷增大的，$log$級別

（可能你懵了，但是沒瓜系，直接看代碼一下子就懂了！）

可以采取可持久化$trie$樹，把$a_i$拆分成二進制存儲

code

#include <cstdio> #define ll long long #define MAX 1000000000 #define MAXN 100005 struct node {int l, r;ll sum; }trie[MAXN * 40]; int n, m, cnt; int root[MAXN], bit[40]; ll a[MAXN];void hex( ll x ) {if( x > MAX ) x = MAX + 1;//a[i]<=1000000000，x只是用來查詢所有<=x的a值和，所以不用設得特別大for( int i = 30;~ i;i -- ) bit[i] = ( x >> i ) & 1; }void insert( int &now, int pre, int id, int w ) {trie[now = ++ cnt] = trie[pre];if( id < 0 ) { trie[now].sum += w; return; }if( ! bit[id] ) insert( trie[now].l, trie[pre].l, id - 1, w );else insert( trie[now].r, trie[pre].r, id - 1, w );trie[now].sum = trie[trie[now].l].sum + trie[trie[now].r].sum; }ll query( int now, int id ) {if( id < 0 || ! now ) return trie[now].sum;if( ! bit[id] ) return query( trie[now].l, id - 1 );else return trie[trie[now].l].sum + query( trie[now].r, id - 1 ); }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) {scanf( "%lld", &a[i] );hex( a[i] );insert( root[i], root[i - 1], 30, a[i] );}for( int i = 1, l, r;i <= m;i ++ ) {scanf( "%d %d", &l, &r );ll last = 0, ans = 1;while( 1 ) {hex( ans );ll tmp = query( root[r], 30 ) - query( root[l - 1], 30 );if( tmp == last ) { printf( "%lld\n", ans ); break; }last = tmp, ans = tmp + 1;}}return 0; }

總結

以上是生活随笔為你收集整理的【2020牛客NOIP赛前集训营-提高组（第一场）题解】（ 牛牛的方程式，牛牛的猜球游戏，牛牛的凑数游戏，牛牛的RPG游戏）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。