Problem - C - Codeforces

思路：

1. 我们从低位凑到高位，因为尽可能unlucky，所以我们保证凑的数字是相同的如1111，4444等（每次前i位相同，其余位数不变）
2. 只要我们当前凑的这个数字符合范围，显然可以推出最优解
3. 注意，我们需要同时从上限r与下限l开始凑，如37与42，如果只凑l，只能凑37，38，39（凑的都是个位数），再凑r（能凑40，41，42）

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\\n"
#define int              long long
#define endll            endl<<endl
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
//---------------------------------------------------------------------------------------------------------------------//
//---------------------------------------------------------------------------------------------------------------------//
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 2e5 + 10;int check(int x)
{set<int>s;while (x){s.insert(x%10);x/=10;}return (*s.rbegin()-*s.begin());
}
void mysolve()
{ll l,r;cin>>l>>r;ll ans=l,p=1;for (int i=1; i<=19; ++i){for (int x=0; x<10; ++x){int tmp=l/p*p+(p-1)/9*x;//l/p*p是先使前面i位变为0，再用(p-1)/9*x保证前面i位是相同的if (tmp>=l&&tmp<=r&&check(tmp)<check(ans))ans=tmp;tmp=r/p*p+(p-1)/9*x;if (tmp>=l&&tmp<=r&&check(tmp)<check(ans))ans=tmp;}p*=10;}cout<<ans<<endl;
}int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll t;cin >> t;while (t--){mysolve();}system("pause");return 0;
}

Problem - D - Codeforces

思路：

1. 要算多少个不匹配需要变化，有亿点困难。我们反过来想，需要的最大操作次数是ans=
2. 如果我们对于位置i数a[i],前面每有一个与它匹配的数，那就ans-1。所以我们可以对于每个数，寻找它前面是不是有在k范围内与它对称的数（且这两个数所属的k区间合法，即区间[l,r],l>=1,r<=n)，有就减一
3. 因此，我们只需要把每个数出现的位置存下来，即v[val]存储的是出现值为val的所有位置。
4. 当然，你肯定会注意到这样存，有可能两个数之间是不匹配的，注意题目说的k为奇数，发现匹配的数奇偶性一定相同，所以我们改为v[val][i],奇偶性分开存储就可。
5. 最后处理就是合法区间了，我们设t在i左边并且与它对称。首先，t>=1,还有区间中点必须左右都有长度为k/2的区间，不够就不合法，即与,最后还有t<=i-2(k=1直接0返回，我们讨论k至少为3）。还有t>=i-k+1,那么我们就可以求出t所属区间[l,r]有多少个符合情况的数

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
const int N = 2e5 + 10;
vector<int>a[N][2];
int32_t main()
{int n,k,x,maxn=-1;cin>>n>>k;for (int i=1; i<=n; ++i){cin>>x;maxn=max(maxn,x);a[x][i&1].push_back(i);//分奇偶性存入}if (k==1)//k=1不需处理{cout<<0<<endl;return 0;}ll ans=(n-k+1)*(k/2);//最多处理次数for (int i=1; i<=maxn; ++i)for (int j=0; j<2; ++j){for (auto &x:a[i][j]){int l=max({1ll,x-k+1,2+k/2*2-x});//每次寻找出现在x之前的值为i的符合区间的数int r=min(x-2,2*n-x-k/2*2);if (l<=r){ans-=upper_bound(a[i][j].begin(),a[i][j].end(),r)-lower_bound(a[i][j].begin(),a[i][j].end(),l);//合法区间里面存在的数个数}}}cout<<ans<<endl;
}

Problem - E1 - Codeforces

思路：

1. 一个串，只要存在一个数（多个数）合法就合法，但是全部不合法才不合法）显然讨论不合法情况比较简单。
2. 假设x符合情况，那么假设sum为所有数和，设x符合，那么有x≡sum-x(mod m),即2x≡sum（mod m)
3. 因为组合情况就是每一位选0~k直接的一个数，我们任意想到背包问题，用dp[i][j]表示当前第i为（要求求取l前面i-1位的所有情况）和为j的不合法情况总数（选不合法，我们只需要保证每一位取的x不合法即可）。
4. 因为sum有k种情况，那么我们枚举所有sum的情况，求出相应sum的不合法个数，然后在求当前sum时每一位选取的数x不满足2*x≡sum(mod m)即可。

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
const int N = 110;int n,k,mod;
ll dp[N][40];
ll qpow(ll base,ll power)
{ll ans=1;while (power){if (power&1)ans=ans*base%mod;power>>=1,base=base*base%mod;}return ans;
}ll tosum(int sum)//求取n位和为sum的不合法数
{memset(dp,0,sizeof(dp));dp[0][0]=1;//这是为了赋值每一位dp[1][j],显然一位数时，不合法情况有k-1种for (int i=1; i<=n; ++i)for (int x=0; x<k; ++x)if (x*2%k!=sum)//转移式是处理了i-1个数，当前第i为选x（它不合法），更新这i位一共和为h的情况{for (int h=0; h<k; ++h)dp[i][h]=(dp[i][h]+dp[i-1][(k+h-x)%k])%mod;}return dp[n][sum];
}int32_t main()
{cin>>n>>k>>mod;ll ans=qpow(k,n);//情况总数for (int i=0; i<k; ++i)ans=(ans+mod-tosum(i))%mod;//枚举sum减去不合法总数cout<<ans<<endl;return 0;
}

家庭教育