BZOJ4724 [POI2017]Podzielno

2019-04-14 09:10发布

站内文章 / 模拟电子
13455 0 1690
先猜结论：一个B进制数+B-1后各位数字之和模B-1意义下不变 证明：+B相当于在次低位+1，-1相当于在最低位-1， 如果某一位加一，如果进位，则下一位会加一，这一位会减去B-1，所以对各位数字之和模B-1意义下的影响是+1 如果某一位减一，如果退位，则下一位会减一，这一位会加上B-1，所以对各位数字之和模B-1意义下的影响是-1 所以原数+B-1后各位数字之和在模B-1意义下不变 那么显然一个B进制数是B-1的倍数的充要条件是各位数字之和模B-1等于0 题里要求让这个数尽量大 那么我们就先把所有数都选上，并且大的数放到高位，然后删去尽量少的数 怎么删呢，我tm想了一天，没想出来，然后看了一眼数据范围，妈的，a[i]>=1，直接删就行（得0就不用删了） 然后前缀和加二分即可 终于800题辣！ #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAXN 1000010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define ll long long #define eps 1e-8 int n,m; ll a[MAXN]; int main(){ int i; ll x=0; scanf("%d%d",&n,&m); for(i=0;i>1; if(a[mid]>=x){ ans=mid; r=mid-1; }else{ l=mid+1; } } printf("%d ",ans); } return 0; } /* */

热门文章