T1 洛阳怀
题解
首先非常容易求出的是所有的 \(\gcd\)
对于 \(\gcd\) 而言，如果它的分数是负数，那么将它除去一定会使这个数列得分变大
所以只用求出所有的 \(\gcd\) 的分数并判断正负以及是否除过当前答案了就可以了
还有一点是因为 \(\gcd\) 是单调不降的，所以可以从后往前查保证当前答案不会超出还未遍历的 \(\gcd\)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define N 2010
using namespace std;
int n,m,ans,a[N],b[N],f[N],g[N];
unordered_map<int,int>mp;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
signed main(){
freopen("cup.in","r",stdin);
freopen("cup.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++){
cin>>a[i];
f[i] = (i==1)?a[1]:gcd(f[i-1],a[i]);
}
for(int i = 1;i<=m;i++){
int x;
cin>>x;
mp[x] = 1;
}
for(int i = 1;i<=n;i++){
int x = f[i];
for(int j = 2;j*j<=f[i];j++){
if(x%j) continue;
int cnt = 0;
while(!(x%j)){
x/=j;
cnt++;
}
if(mp[j]) g[i]-=cnt;
else g[i]+=cnt;
}
if(x!=1){
if(mp[x]) g[i]--;
else g[i]++;
}
}
int tag = 1,flag = 0;
for(int i = n;i>=1;i--){
while(g[i]-flag<0&&f[i]/tag>1){
ans-=(g[i]-flag)*i;
tag = f[i];
flag = g[i];
}
}
for(int i = 1;i<=n;i++){
int x = a[i];
for(int j = 2;j*j<=a[i];j++){
if(x%j) continue;
int cnt = 0;
while(!(x%j)){
x/=j;
cnt++;
}
if(mp[j]) ans-=cnt;
else ans+=cnt;
}
if(x!=1){
if(mp[x]) ans--;
else ans++;
}
}
cout<<ans;
return 0;
}
T2 青天之谊
题解
对于每个点，用 \(dfs\) 求出所有人到这个点的最少时间
考虑青见能走到哪些点
-
起始点可以走到
-
如果一个点可以走到，并且这个点要比其他人早一天到，那么后面一天可以继续走到下面的点
-
如果一个点可以走到，并且这个点和其他人能在同一天到，但是同一天青见可以继续走
最优的相遇时间是对于青见能走到的点，天吾走到的最短时间和青见走到的时间取 \(\max\) 的最大值
#include<bits/stdc++.h>
#define N 500010
using namespace std;
struct edge{
int v,ne,w;
}e[N<<1];
int n,cnt,tot,st,sp,ans,mn,stq,h[N],d[4][N];
void add(int u,int v,int w){
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].ne = h[u];
h[u] = cnt;
}
void dfs(int f,int x,int fa,int noko){
for(int i = h[x];i;i = e[i].ne){
int v = e[i].v;
if(v!=fa){
if(e[i].w>sp) continue;
d[f][v] = d[f][x];
if(e[i].w>noko){
d[f][v]++;
dfs(f,v,x,sp-e[i].w);
}else dfs(f,v,x,noko-e[i].w);
}
}
}
void check(int x,int y){
mn = n+1;
for(int j = 1;j<=tot;j++) mn = min(mn,d[j][x]);
ans = max({ans,mn,d[0][x]});
if(d[0][x]>mn) return ;
for(int i = h[x];i;i = e[i].ne)
if(e[i].v!=y&&(d[0][x]<mn||d[0][x]==d[0][e[i].v]))
check(e[i].v,x);
}
int main(){
freopen("chase.in","r",stdin);
freopen("chase.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
cin>>tot;
for(int i = 0;i<=tot;i++){
for(int j = 1;j<=n;j++) d[i][j] = n+1;
cin>>st>>sp;
if(!i) stq = st;
d[i][st] = 0;
dfs(i,st,0,0);
}
check(stq,0);
if(ans==n+1) ans = -1;
cout<<ans;
return 0;
}
就挺抽象的
T3 数数
题解
奉劝各位不要从最高位往最低位处理
某sb考试就这么G了，太麻烦了
从低位向高位 枚举一个前缀与 \(x\) 一致，接下来的一位比 \(x\) 小
考虑一下此时后面位的取值就是还没有被确定的那些位的任意选择
我们用并查集把限制关系维护一下就行了
#include<bits/stdc++.h>
#define int long long
#define mod 19260817
#define N 100010
using namespace std;
int n,m,l[N],r[N],fa[N],num[N],mn[N],mx[N];
int ksm(int a,int b){
int res = 1;
while(b){
if(b&1) res = res*a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
int find_(int x){
return x==fa[x]?x:fa[x] = find_(fa[x]);
}
int solve(int *a){
int tot = 0,ans = 0;
for(int i = 1;i<=n;i++)
if(fa[i]==i) tot++;
for(int i = n;i>0;i--){
if(fa[i]==i){
tot--;
ans = (ans+a[i]*ksm(10,tot)%mod)%mod;
}
if(a[find_(i)]<a[i]) ans = (ans+ksm(10,tot))%mod;
if(a[find_(i)]!=a[i]) break;
}
return ans;
}
signed main(){
freopen("counting.in","r",stdin);
freopen("counting.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++)
fa[i] = i;
for(int i = 1;i<=n;i++)
cin>>l[i];
for(int i = 1;i<=n;i++)
cin>>r[i];
cin>>m;
for(int i = 1;i<=n;i++){
int u,v;
cin>>u>>v;
u = find_(u);v = find_(v);
fa[min(u,v)] = max(u,v);
}
int ans = (solve(r)-solve(l)+mod)%mod;
cout<<ans;
return 0;
}
T4
没写，略过
标签：校内,gcd,int,230930,fa,ans,mod,define From： https://www.cnblogs.com/cztq/p/17743473.html