第三题换成能否得到x, 可以1， 不可以-1
题解：
第一题：打表找规律；
打表发现a是：1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9……
对于每一项Ai = i拆分成质因数中有多少个2 + 1；如果把桶也给打出来，就发现他是这样的：
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 +
2 + 4 + 6 + 8 +
4 + 8 +
8 +
即2^i的等差数列，所以对一个数m我们就很容易确定他前面的数的和；
但是对于一个位置我们怎么找到他对应的m呢？
把上面那个式子换成每项为1就知道他前面有多少项了；
我们可以二分m,找到Ai前一个数m - 1，然后推出有多少个重复m;
#include<bits/stdc++.h> using namespace std; #define ll long long const int mod = 1000000007; const ll v2 = 500000004; ll ksm(ll a, ll b){ ll ret = 1; for(; b>>=1; a=a*a%mod) if(b&1)ret=ret*a%mod; return ret; } inline ll dc(ll a1, ll an, ll n){ return (a1 % mod + an % mod) % mod * (n % mod) % mod * v2 % mod; } ll check(ll a){ ll k = 1, ret = 0; while(k <= a){ ret += a/k; k <<= 1; } return ret + 1; } ll work(ll a){ if(!a)return 0; if(a == 1 || a == 2) return 1; ll lf = 1, rg = 1e18, ax; while(lf <= rg){ ll mid = (lf + rg) >> 1; if(check(mid) < a)ax = mid, lf = mid + 1; else rg = mid - 1; } ll k = 1, ans = 0; while(k <= ax){ ans = (ans + dc(k, ax / k * k, ax / k)) % mod; k <<= 1; } return ((ax + 1) % mod * (a - check(ax)) % mod + ans + 1) % mod; } int main(){ freopen("me.in","r",stdin); freopen("me.out","w",stdout); ll L, R; cin>>L>>R; cout<<(work(R) - work(L - 1) + mod) % mod<<endl; }
第二题：数据范围暗示dp;
dp[ i ][ s ] 表示我从小到大放数考虑到第i个数，现在 Sum(p) = j的方案数；
如果我当前放的数是最大的，那么整个序列就分成了前后两段互不影响的序列；所以我当前的贡献s 就是:
左边的贡献 * 右边的贡献 * c[i - 1][j] + min(j + 1, i - j) (当前数放在 j 这个位置后面, 第一段的贡献确定，数大小相对位置确定，所以该位随便填什么，只要相对大小确定就好了，所以乘上i - 1个数中选j个数的方案数）；
这道题还有一个烟雾弹，x <= 100000, 其实x不可能达到很的数， n <= 80, 一个数最大为40， 他要是为40， 旁边就不会有39了，所以最后这个和是很小的；
枚举i, 位置j, 左右贡献，复杂度其实很优
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod = 998244353; ll dp[85][10005], c[85][85]; int mx[85]; void init(){ for(int i = 0; i <= 80; i++) for(int j = 0; j <= i; j++) if(i == 0 || j == 0)c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } int main(){ freopen("good.in","r",stdin); freopen("good.out","w",stdout); int n, x, cnt = 0; scanf("%d%d", &n, &x); dp[0][0] = 1; init(); for(int i = 1; i <= n; i++) for(int j = 0; j < i; j++) for(int k = 0; k <= mx[j]; k++) for(int kk = 0; kk <= mx[i - j - 1]; kk++){ dp[i][k + kk + min(j + 1, i - j)] = (dp[i][k + kk + min(j + 1, i - j)] + (dp[j][k] * dp[i - j - 1][kk]) % mod * c[i - 1][j] % mod) % mod; mx[i] = max(mx[i], k + kk + min(j + 1, i - j)); } printf("%d ", dp[n][x]); }
第三题：一道神奇解法的题
x小的时候可以背包，但x大了怎么办；
贪心思想，先放最大的，剩下一小部分用其他填；
我们先全用大的填满，就会多出一截，可以用小的去换他，就相当于去消去这部分；比如多了10 就可以用5个2去替换10，所以每张牌贡献就是an - ai,我们最后只需知道是否可以替换多的部分就好了；但会出现一个情况 原来是5 5 5 5，现在用4 4 4 4 4 去替换，这是不合法的，因为前面5不够换了；所以记录替换成x的最少替换次数，如果当前值+ai >= an, 我们就可以用原来的an,不然就要多花一张牌来替换，这个东西可以用SPFA。。。
最后判断 dis[多的部分] <= 我原本的牌数；
#include<bits/stdc++.h> using namespace std; #define ll long long const int M = 100000+5, inf = 1e9; ll dis[M]; int a[88]; queue <int> Q; bool inq[M]; int main(){ freopen("hungry.in","r",stdin); freopen("hungry.out","w",stdout); int n, q; scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++)scanf("%d", a + i); sort(a + 1, a + 1 + n); for(int i = 1; i < n; i++)a[i] = a[n] - a[i]; ll x = 0; memset(dis, -1, sizeof(dis)); inq[0] = 1; Q.push(0); dis[0] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 1; i < n; i++){ ll w = dis[u]; int to = u + a[i]; // printf("%d %d %I64d ", u,to,w); if(to >= a[n])to -= a[n]; else w++; // printf("%d %d %I64d ",u,to, w); if(dis[to] > w || dis[to] == -1){ dis[to] = w; if(!inq[to]){ Q.push(to); inq[to] = 1; } } } } while(q--){ scanf("%I64d", &x); int own = (1LL*a[n] + x - 1) / (1LL*a[n]); int res = 1LL*a[n] * own - x; if(dis[res] > own || dis[res] == -1)puts("-1"); else puts("1"); } }
今天是我的暴力专场，第一题想推通项公式，但是他在下标下面，很明显没有，而且我也没有打桶的表，后两道题实在是在能力之外；
然而今天yl大佬又接近AK，%%%，不论题难或不难都是AK或AK边缘，tql