T1：牛牛的方程式
title
solution
因为浮点错误炸了70pts
这个三元一次不定方程呢，其实也没有特别难
只需要在二元一次不定方程(Ax+By=C)上面略作变化即可！
将其转化为二元一次不定方程，假设(c，z)为已知量
此时可以直接套用(exgcd)解出(Ax+By=1……③)的特殊值(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 imes b imes c≠0)
这个情况什么意思呢？就是在上面三元一次转二元一次最后判断(z)是否有解的时候
(z)可能等于(0)，那么就需要满足(gcd(a,b)|d)即可
具体详见代码——
code
#include <cstdio>
#include <iostream>
using namespace std;
#define ll long long
void 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
" );
continue;
}
if( ! a && ! b && ! c ) {
printf( "NO
" );
continue;
}
if( ! a && ! b ) {
if( d % c ) printf( "NO
" );
else printf( "YES
" );
continue;
}
if( ! a && ! c ) {
if( d % b ) printf( "NO
" );
else printf( "YES
" );
continue;
}
if( ! b && ! c ) {
if( d % a ) printf( "NO
" );
else printf( "YES
" );
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
" );
else printf( "NO
" );
}
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
", p[9] );
}
return 0;
}
T3：牛牛的凑数游戏
title
solution
一. 首先10pts的暴力，肯定是基本功过硬，前缀和能拿到
暴力yyds！！
二. 比赛时，我对【输入的(a_i)为(2)的非负整数幂】这个暴力分有很大的想法
因为每个数都有对应的二进制，意思就是如果(2)的每一个幂都被包含在区间里的话，每两个幂之间的数都可以被凑出来
但是我发现自己的时间复杂度(O(n^2logn))
牛客的出题人真的蛮良心的了，这两个部分分的思路组合起来，差不多就是正解那个方向了
通过第一个暴力的前缀和可得
([1,i])的(a)值和(+1)如果小于(a_{i+1})，那么((sum_{i=1}^ia_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
", ans ); break; }
last = tmp, ans = tmp + 1;
}
}
return 0;
}