at场
T1 花间叔祖
原题 [ARC148A] mod M
考虑每个数都写成 \(k\cdot mod+b\) 的形式，然后将找出所有相邻两数差的 \(gcd\)，如果 \(gcd\ne 1\) 的话选 \(mod=2\) 这样最优，否则选 \(gcd\) 这样答案为 \(1\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int a[N],n,mod,d[N];
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();
for(int i=1;i<=n;++i)a[i]=read();
std::sort(a+1,a+n+1);
for(int i=2;i<=n;++i)d[i]=a[i]-a[i-1];
int gcd=d[2];
for(int i=2;i<=n;++i)gcd=std::__gcd(gcd,d[i]);
std::cout<<(gcd==1?2:1)<<'\n';
}
T2 合并r
原题 [ARC107D] Number of Multisets
考虑与朴素的背包相比它更多的性质。
我们只考虑 \(1\) 的贡献，发现一个构成 \(k\) 的方案，一定可以构成 \(k/2\)，相当于将所有组成除以二，然后就做完了。
这样为什么是对的，因为我们的转移只有两种，增加元素或者将元素变换，前者对应了 \(f_{i-1,j-1}\)，后者对应了 \(f_{i-1,2j}\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e4+10,mod=998244353;
int n,m,f[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
f[1]=1;
for(int i=2;i<=n;++i)for(int j=i;j;--j){
f[j]=f[j-1]+f[j*1];
f[j]-=(f[j]>=mod)*mod;
}
cout<<f[m]<<'\n';
}
T3 回收波特
不会
标签：typedef,ch,gcd,int,long,CSP,模拟,mod From： https://www.cnblogs.com/Ishar-zdl/p/18327230