比赛地址
Pro: 5/5/12
Rank: 161/975
[A] Groundhog and 2-Power Representation
题意&题解
签到题
Python大法好
代码
s=input()
a=s.replace('(','**(')
print(eval(a))
[E] Groundhog Chasing Death
题意
求\Pi_{i=a}^{b}\Pi_{j=c}^{d}Gcd(x^{i},y^{j})
题解
先分解质因子,然后计算每个质因子的贡献.如果某个质因子是两个数共有的,就计算一下其指数在哪个范围的时候,gcd的结果取第一个数的因子,以及在哪个范围内取第二个数的因子,累计起来即可.需要卡一下常数.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define mo 998244353LL
#define mi(__x,__y) ({ \
long long int __p=__x,__t=1,__Re=1; \
for (;__t<=__y;(__t&__y)?__Re=(__Re*__p)%mo:0,__p=(__p*__p)%mo,__t<<=1); \
__Re; \
})
long long int a, b, c, d, x, y;
long long int xi[200005], yi[200005], s[50][50];
long long int fx[200005], fxt[200005], fy[200005], fyt[200005];
long long int totx = 0, toty = 0;
long long int ask(int a, int b, int c, int d) {
long long int ans = 1;
int st1 = 1, st2 = 1;
while(st1 <= totx && st2 <= toty) {
if (fx[st1] < fy[st2]) { st1++; continue; }
if (fx[st1] > fy[st2]) { st2++; continue; }
int p = fxt[st1], q = fyt[st2], k = fx[st1];
if (s[p][q] != -1) {
ans = (ans * mi(k, s[p][q])) % mo;
st1++; st2++;
continue;
}
s[p][q] = 0;
int i, aim = 0;
for (i = a; i <= b; i++) {
long long int tp = 1LL * i * p / q;
if (tp < c) { aim = i;}
else break;
}
if (aim) {
long long int g1 = (1LL*p*(d-c+1)%(mo-1))*(1LL*(a+aim)*(aim-a+1)/2%(mo-1))%(mo-1)+mo-1;
ans = (ans * mi(k, g1)) % mo; s[p][q] += g1;
}
for (; i <= b; i++) {
long long int tp = 1LL * i * p / q;
if (tp < d) {
long long int gg = (1LL*p*i*(d-tp)%(mo-1))+(1LL*q*(c+tp)*(tp-c+1)/2%(mo-1))+mo-1;
ans = (ans * mi(k, gg)) % mo; s[p][q] += gg;
} else {
long long int g = 1LL*q*(c+d)*(d-c+1)/2%(mo-1)*(b-i+1)%(mo-1)+mo-1;
ans = (ans * mi(k, g)) % mo; s[p][q] += g;
break;
}
}
s[p][q] = s[p][q] % (mo-1) + mo - 1;
st1++; st2++;
}
return ans;
}
int main(){
//freopen("1.txt", "r", stdin);
scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &x, &y);
long long int p;
p = sqrt(x)+1;
for (int i = 1; i <= 35; i++) for (int j = 1; j <= 35; j++) s[i][j] = -1;
for (int i = 2; i <= p; i++) {
if (x==0) break;
int flag = 0;
while(x%i==0) {
xi[i]++; x/=i; flag = 1;
}
if (flag) {
fx[++totx] = i;
fxt[totx] = xi[i];
}
}
if (x != 1 && x != 0) {
fx[++totx] = x;
fxt[totx] = 1;
}
p = sqrt(y)+1;
for (int i = 2; i <= p; i++) {
if (y==0) break;
int flag = 0;
while(y%i==0) {
yi[i]++; y/=i; flag = 1;
}
if (flag) {
fy[++toty] = i;
fyt[toty] = yi[i];
}
}
if (y != 1 && y != 0) {
fy[++toty] = y;
fyt[toty] = 1;
}
//for (int i = 1; i <= totx; i++) printf("%d %d\n", fx[i], fxt[i]);
//for (int i = 1; i <= toty; i++) printf("%d %d\n", fy[i], fyt[i]);
long long int ans = ask(a, b, c, d);
printf("%lld\n", ans);
return 0;
}
[F] Groundhog Looking Dowdy
题意
有n个集合,每个集合中有一些数.现在要从每个集合中取出一个数,然后再从这些数中取出m个,使得这些数的极值差最小.求这个最小值.
题解
二分答案.
把所有数从小到大排序,二分极值差,然后用一个滑动窗口一样的东西遍历排好序的序列,如果在某个时刻窗口中的数来自不同的至少m个集合,就认为该答案合法.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 2000010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,j,low,high,mid,ans,x,cnt;
int v[N];
struct Data{
int x,id;
}a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
inline bool cmp(const Data &a,const Data &b){return a.x<b.x;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL bool Check(int x){
reg int i=0,l=0,r=1,L=0,R=0,sum=0;
for (i=1;i<=n;i++) v[i]=0;
l=r=1; L=a[1].x; v[a[1].id]++; sum=1;
while (l<cnt){
while (r<cnt && a[r+1].x-L <= x){
r++; v[a[r].id]++;
if (v[a[r].id]==1) sum++;
if (sum>=m){
// cout<<l<<" "<<r<<" "<<x<<endl;
return 1;
}
}
v[a[l].id]--;
if (!v[a[l].id]) sum--;
l++; L=a[l].x;
if (r<l){
v[a[l].id]++;
if (v[a[l].id]==1) sum++;
r=l;
}
}
return 0;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
if (m==1){
puts("0"); return 0;
}
for (i=1;i<=n;i++){
x=read();
for (j=1;j<=x;j++){
++cnt;
a[cnt].x=read(); a[cnt].id=i;
}
}
sort(a+1,a+1+cnt,cmp);
a[cnt+1].x=0x7f7f7f7f;
low=0; high=INF;
while (low<=high){
mid=(low+high)>>1;
if (Check(mid)) ans=mid,high=mid-1;
else low=mid+1;
}
cout<<low<<endl;
// cout<<ans<<endl;
return 0;
}
[I] The Crime-solving Plan of Groundhog
题意
给出n个数,要求把它们拼成两个数,使得这两个数的积最小.
题解
贪心.第一个数是一个一位数,为给出的数中最小的数.剩下的数按照从小到大的次序排成第二个数.注意不要带前导零.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int T,n,i,x,len;
int a[N],s[15],Ans[N*4];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read();
for (i=1;i<=n;i++) a[i]=read();
if (n==2){
printf("%d\n",a[1]*a[2]);
continue;
}
len=0; x=0;
memset(s,0,sizeof(s));
for (i=1;i<=n;i++) s[a[i]]++;
for (i=1;i<=9;i++)
if (s[i]){
x=i; s[i]--; break;
}
for (i=1;i<=9;i++)
if (s[i]>0){
s[i]--; Ans[++len]=i;
break;
}
if (s[0]){
while (s[0]--) Ans[++len]=0;
}
for (i=1;i<=9;i++)
if (s[i]>0){
while (s[i]--) Ans[++len]=i;
}
reverse(Ans+1,Ans+1+len);
for (i=1;i<=len;i++) Ans[i]*=x;
for (i=1;i<=len;i++)
if (Ans[i]>=10) Ans[i+1]+=Ans[i]/10,Ans[i]%=10;
if (Ans[len+1]) ++len;
for (i=len;i;i--) printf("%d",Ans[i]);
putchar(10);
for (i=len;i;i--) Ans[i]=0;
}
return 0;
}
[K] The Flee Plan of Groundhog
题意
有两个人在一棵树上玩追逐战,追人的那个速度是2个节点每秒,被追的那个是1个节点每秒.假如两个人都采用最优策略,求被追的人最晚会在什么时候被抓住.
题解
以追人的位置为根建树.显然,被追的人的逃跑路线一定是先从当前位置沿父节点走到某个节点上,然后一直走到该节点最深的儿子的位置.所以预处理下每个节点最深的儿子有多深,然后从被追的人的位置往上枚举即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,t,lsum=1,x,y,now,ans,Ans,L;
int head[N],dis[N][2],d[N],h[N],f[N];
vector <int> son[N];
struct Edge{
int t,next,l;
}e[N*8];
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Dfs(int x,int fa,int d,int p){
reg int i=0;
dis[x][p]=d;
for (i=head[x];i;i=e[i].next){
if (e[i].t==fa) continue;
Dfs(e[i].t,x,d+1,p);
}
}
IL void Maketree(int x,int fa){
reg int i=0;
h[x]=d[x];
for (i=head[x];i;i=e[i].next){
if (e[i].t==fa) continue;
d[e[i].t]=d[x]+1; f[e[i].t]=x;
son[x].push_back(e[i].t);
Maketree(e[i].t,x);
h[x]=Max(h[x],h[e[i].t]);
}
}
IL void DP(int x,int val){
reg int l=0;
if (!x) return;
if (L<=3*val) return;
l=h[x]-d[x];
if (l<=L-3*val){
ans=l; l=L-3*val-l;
ans+=(l+1)>>1;
Ans=Max(Ans,ans+val);
} else
Ans=Max(Ans,L-3*val+val);
DP(f[x],val+1);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); t=read();
if (n==1){
puts("0"); return 0;
}
for (i=1;i<n;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
Dfs(1,0,0,0); Dfs(n,0,0,1);
if (dis[n][0]<=t){
puts("0"); return 0;
}
for (i=1;i<=n;i++)
if (dis[i][0]==t && dis[i][0]+dis[i][1]==dis[n][0]){
now=i; break;
}
Ans=(dis[now][1]+1)>>1; L=dis[now][1];
Maketree(n,0); DP(now,0);
cout<<Ans<<endl;
return 0;
}
总结
解题的技巧性还是有待提升,比如B题的策略和国王游戏就比较像,J题0转-1想到了,离化成前缀和模型差了一点点.接下来应该多刷点Atcoder?
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第九场
本文地址: 2020牛客暑期多校第九场
