2020校赛 D逛校园 E 布阵排兵 F 因子补题

本文主要是介绍2020校赛 D逛校园 E 布阵排兵 F 因子补题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

稳定亚军使人懒惰！！！
只贴代码！！！

D 逛校园

#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
using namespace std;
const int N = 1e5 + 5;ll Case,n;
char op;
ll x,nx,ny,nd;
ll dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
ll diff[4005][4005];void print(){for(int i=2000-10;i<=2000+10;i++){for(int j=2000-10;j<=2000+10;j++){printf("%d ",diff[i][j]);}puts("");}
} 
void solve(){ll res = 0;scanf("%lld",&n);nx = 2000,ny = 2000;for(int i=1;i<=n;i++){getchar();scanf("%c %lld",&op,&x);int x1 = nx, y1 = ny;if(op=='R') nd++;else if(op=='L') nd--;else if(op=='D') nd += 2;nd=(nd+4)%4; int x2 = nx + dir[nd][0]*x;int y2 = ny + dir[nd][1]*x;if(nd == 0|| nd == 1){diff[x1][y1] += 1;diff[x1][y2+1] -= 1;diff[x2+1][y1] -= 1;diff[x2+1][y2+1] += 1;}else{diff[x2][y2] += 1;diff[x2][y1+1] -= 1;diff[x1+1][y2] -= 1;diff[x1+1][y1+1] += 1;}nx = x2,ny = y2;}for(int i=1;i<=4000;i++) {for(int j=1;j<=4000;j++) {if(diff[i][j]+=diff[i][j-1]+diff[i-1][j]-diff[i-1][j-1]) res++;}}//print();printf("%lld",res);
}int main(){//init();Case=1;//scanf("%d",&Case);while(Case--){solve();}return 0;
}

E 布阵排兵

#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {inline void input(int& res) {char c = getchar();res = 0;int f = 1;while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }res = f ? res : -res;}inline ll qpow(ll a, ll b) {ll ans = 1, base = a;while (b) {if (b & 1) ans = (ans * base % mod +mod )%mod;base = (base * base % mod + mod)%mod;b >>= 1;}return ans;}
}
using namespace fastIO;
const int N = 1e5 + 5;int Case,n;
ll p,x;
map<ll,ll> zr;
vector<ll> v[N];void solve(){ll res = 0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld %lld",&p,&x);if(!zr.count(p)) zr[p]=i;v[zr[p]].push_back(x);}for(auto i:zr){ll t1 = i.first,t2 = i.second;int len = v[t2].size();sort(v[t2].begin(),v[t2].end());for(int j=62;j>=0;j--) {for(int k=len-1;k>=0;k--){if((v[t2][k]>>j)&1){if(((res>>j)&1) == 0)res ^= v[t2][k];for(int t=len-1;t>=0;t--){if(((v[t2][t]>>j)&1)&&t!=k){v[t2][t]^=v[t2][k];}}v[t2][k]=0;break;}}}}printf("%lld",res);
}int main(){//init();Case=1;//scanf("%d",&Case);while(Case--){solve();}return 0;
}

F 因子

#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 998244353;
using namespace std;
const int N = 1e5 + 5;ll Case,n,m,op,x;
ll tree[25][N];ll a[N];int prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};ll getnum(int x,int p){ll cnt = 0;while(x%p==0){cnt++;x/=p;}return cnt;
} int lowbit(int x){return x&(-x);
}void updata(ll i,ll k,ll t){    //在i位置加上k//printf("%lld %lld %d\n",i,k,prime[t]);while(i <= n){tree[t][i] += k;i += lowbit(i);}
}ll getsum(ll i,ll t){        //求A[1 - i]的和ll res = 0;while(i > 0){res += tree[t][i];res %= mod;i -= lowbit(i);}return res;
}
void solve(){scanf("%d %d",&n,&m);for(ll i=1;i<=n;i++){scanf("%lld",&x);a[i]=x;for(ll j=0;j<20;j++){ll t = getnum(x,prime[j]);updata(i,t,j);}}while(m--){scanf("%lld",&op);if(op==1){ll x,k;scanf("%lld %lld",&k,&x);for(ll j=0;j<20;j++){ll t = getnum(a[k],prime[j]);updata(k,-t,j);}for(ll j=0;j<20;j++){ll t = getnum(x,prime[j]);updata(k,t,j);}a[k]=x;}else if(op==2){ll l,r;ll res = 1;scanf("%lld %lld",&l,&r);for(int i=0;i<20;i++){ll t1 = getsum(l-1,i);ll t2 = getsum(r,i);//cout<<prime[i]<<" "<<t1<<" "<<t2<<endl;res = res *(t2 - t1 + mod + 1)%mod;res %= mod;}printf("%lld\n",res);}}
}int main(){//init();Case=1;//scanf("%d",&Case);while(Case--){solve();}return 0;
}