2023.8.2

2022河南萌新联赛第（三）场：河南大学\神奇数字.cpp

//题意：给定三个正整数a b c,求x满足满足abc同余x的个数。

//这个考虑同余的性质，就是两个数的差去取模为0的数肯定是这两个数的同余数,。因此我们计算三个数两两之间差的最大公约数，然后直接分解质因数，计算gcd的因子个数就是x能够用取到的数量。

#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;int n,m;int a[N];int gcd(int a,int b){return !b?a:gcd(b,a%b);}void solve(){int a,b,c;cin>>a>>b>>c;if(a==b&&a==c){cout<<-1<<'\n';return ;}int x=gcd(abs(a-b),abs(b-c));vector<int>v;for(int i=1;i*i<=x;i++){if(x%i==0){if(i!=x/i)v.push_back(x/i);v.push_back(i);}}sort(v.begin(),v.end());fr(i,0,v.size()-1){cout<<v[i]<<' ';}cout<<'\n';}signed main(){int t=1;cin>>t;while(t--) solve();return 0;}

总结：//同余的性质 (就是两个数的差去取模为0的数肯定是这两个数的同余数)
//同余式可逐项相加
//同余式可以逐项相乘。
//同余式一边的数可以移到另一边，只要改变符号就可以了
//同余式的每一边都可以增加或减去模的任意倍数。
//同余式两边的数如有公约数，此公约数又和模互素，那么就可以把两边的数除以这个公约数。
//同余式两边的数和模可以同时乘上一个整数。
//同余式两边的数和模可以同时被它们任一公约数除。
//如果同余式对于模m成立，那么它对于m的任意约数相等的模d也成立。
//如果同余式一边上的数和模能被某个数除尽，则同余式的另一边的数也能被这个数除尽。
//同余式一边上的数与模的最大公约数，等于另一边上的数与模的最大公约数

2022河南萌新联赛第（三）场：河南大学\逆序对计数.cpp

//题意：给定长度为n的排列（0<=n<=6000）,每次询问为如果将l,r翻转，则逆序对的个数

//思路： 对于一个排列, 如果区间反转, 逆序数等于区间中所有的对数减去当前的逆序对数, 即原本的正序对变为逆序对, 原本的逆序对变为正序对。

//改变区间在整个区间的位置不重要，逆序对的增减只会在区间进行

/* #include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;int n,m;int a[N];int s[6010][6010];int change(int l,int r){int len=r-l+1;int x=len*(len-1)/2;return x-2*s[l][r];}void solve(){cin>>n;fr(i,1,n){cin>>a[i];}int res=0;fr(i,1,n){           //预处理所有l,r的逆序数个数fr(j,1,i){s[j][i]=s[j][i-1];}int cnt=0;ufr(j,i-1,1){if(a[j]>a[i]){cnt++;res++;}s[j][i]+=cnt;}}cin>>m;while(m--){int l,r;cin>>l>>r;cout<<res+change(l,r)<<'\n';}}signed main(){int t=1;//   cin>>t;while(t--) solve();return 0;} *///树状数组做法#include<bits/stdc++.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<queue>#include<cstring>#include<math.h>#include<map>#include<vector>#include<stack>using namespace std;#define endl '\n'typedef pair<int,int> pr;#define int long long#define ll long long#define fr(i,l,r) for(int i=l;i<=r;i++)#define ufr(i,n,z) for(int i = n;i >= z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N = 1e6+10;const int mod=998244353,inf=LONG_LONG_MAX;int n,m;int a[N];int t[N];int f[6010][6010];void add(int x){for(int i=x;i<=n;i+=i&-i){t[i]+=1;}}int query(int x){int ans=0;for(int i=x;i;i-=i&-i){ans+=t[i];}return ans;}void solve(){cin>>n;fr(i,1,n){cin>>a[i];}fr(i,1,n){fr(j,i,n){f[i][j]=f[i][j-1]+(j-i-query(a[j]));         //(j-i-query(a[j])即区间-正序对个数add(a[j]);}fr(j,1,n){t[j]=0;}}cin>>m;int res=f[1][n];while(m--){int l,r;cin>>l>>r;cout<<res+(r-l+1)*(r-l)/2-2*f[l][r]<<'\n';}}signed main(){int t=1;//   cin>>t;while(t--) solve();return 0;}

P1045 [NOIP2003 普及组] 麦森数(高精度快速幂)
题意：输入P(1000<=p<=3100000)，输出2^p-1的位数及最后500位数
 

#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
int f[1001], p, res[1001], sav[1001];//乘法要开两倍长度
void result_1() {memset(sav, 0, sizeof(sav));for (register int i = 1; i <= 500; i += 1)for (register int j = 1; j <= 500; j += 1)sav[i + j - 1] += res[i] * f[j];//先计算每一位上的值（不进位）for (register int i = 1; i <= 500; i += 1){sav[i + 1] += sav[i] / 10;//单独处理进位问题，不容易出错sav[i] %= 10;}memcpy(res, sav, sizeof(res));//cstring库里的赋值函数，把sav的值赋给res
}
void result_2() {memset(sav, 0, sizeof(sav));for (register int i = 1; i <= 500; i += 1)for (register int j = 1; j <= 500; j += 1)sav[i + j - 1] += f[i] * f[j];for (register int i = 1; i <= 500; i += 1){sav[i + 1] += sav[i] / 10;sav[i] %= 10;}memcpy(f, sav, sizeof(f));
}
int main() {cin >> p;cout << int(log10(2) * p + 1) << '\n';               //2^p-1,2^p的位数res[1] = 1;f[1] = 2;while (p) {if (p % 2 == 1) {result_1();}result_2();p >>= 1;}res[1] -= 1;for ( int i = 500; i >= 1; i--)//注意输出格式，50个换一行，第一个不用if (i != 500 && i % 50 == 0)printf("\n%d", res[i]);else printf("%d", res[i]);return 0;
}

数位dp

(最高位限制，记忆化搜索，枚举位的大小，前导0)

洛谷P2657 [SCOI2009] windy 数

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

#include<iostream>
#include<cstring>
using namespace std;
int num[12], dp[12][12];
int dfs(int pos, int pre, int limit, int lead) {int ans = 0, i, up;if (pos == -1)  //搜完return 1;      //用作计数if (!limit && dp[pos][pre] != -1 && !lead)//没有最高位限制，已经搜过了,并且没有前导0return dp[pos][pre];      //记忆化搜索up = limit ? num[pos] : 9;//当前位最大数字 for (i = 0; i <= up; i++) {//从0枚举到最大数字 if (lead) {//有前导0不受限制 ans += dfs(pos - 1, i, limit && i == up, lead && i == 0);}else if (i - pre >= 2 || i - pre <= -2)//无前导0受限 ans += dfs(pos - 1, i, limit && i == up, lead && i == 0);}if (!limit && !lead)//没有最高位限制且没有前导0时记录结果 dp[pos][pre] = ans;return ans;
}
int solve(int x) {int pos = 0;while (x) {num[pos++] = x % 10;x /= 10;}   //按位储存return dfs(pos - 1, -1, 1, 1);
}
int main() {ios::sync_with_stdio(false);int lt, rt;cin >> lt >> rt;memset(dp, -1, sizeof(dp));cout<< solve(rt) - solve(lt - 1)<<'\n';return 0;
}