2020牛客暑期多校训练营(第九场)

8.08 体验极差的牛客9

A-Groundhog and 2-Power Representation

题意

给一个式子,每个括号前省略了一个 ^ 符号,问式子运算后的结果。

思路

卡语言是真的恶心,Python 一行就行,真的没意思,体验极差

倒着模拟记录状态,Java 写的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.math.*;
import java.util.*;
import java.io.*;
public class Main {
public static BigInteger qpow(BigInteger a,BigInteger b){
BigInteger ans=BigInteger.ONE;
while(b.compareTo(BigInteger.ZERO)>0){
if(b.mod(new BigInteger("2")).compareTo(BigInteger.ONE)==0) ans=ans.multiply(a);
b=b.divide(new BigInteger("2")); a=a.multiply(a);
} return ans;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
BigInteger[] a=new BigInteger[20005];
BigInteger res=BigInteger.ZERO;
BigInteger two=new BigInteger("2");
BigInteger ten=new BigInteger("10");
// solve
int len=s.length(),cnt=0;
for(int i=0;i<len;i++) a[i]=BigInteger.ZERO;
for(int i=len-1;i>=0;i--){
if(s.charAt(i)==')'){
cnt++;
}
else if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
res=BigInteger.valueOf(s.charAt(i)-'0');
}
else if(s.charAt(i)=='+'){
a[cnt]=a[cnt].add(res); res=BigInteger.ZERO;
}
else if(s.charAt(i)=='('){
a[cnt]=a[cnt].add(res);
res=BigInteger.ZERO;
BigInteger t=qpow(two,a[cnt]);
cnt--; a[cnt]=a[cnt].add(t);
a[cnt+1]=BigInteger.ZERO;
i--;
}
} System.out.println(a[0]);
}
}

E-Groundhog Chasing Death

题意

给定 $a$ 、$b$ 、$c$ 、$d$ 、$x$ 、$y$ ,求 $\prod \limits^{b} _ {i=a}\prod \limits^{d} _ {j=c}gcd(x^i,y^j)$ 。

思路

只需要考虑公共质因数。记录 $x$ 和 $y$ 的公共质因数在 $x$ 、$y$ 分别出现的次数,对于每个公共质因数,枚举 $x$ 的每个幂次,每次求 $y$ 在 $[c,d]$ 幂次中的和 $x$ 此幂次的大小关系,取最小个数计算。

坑点

这种写法有个数炸 long long ,赛后想到可以取模降幂的哦

upd:取模还没 __int128 快,就这

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%lld", &x)
#define rep(i,s,e) for(ll i=(s); i<(e); ++i)
#define dep(i,e,s) for(ll i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll maxn = 1e5 + 5;
const ll mod = 998244353;
map<ll,ll>mp1,mp2;
ll qpow(ll a,__int128 b){
ll ans=1; while(b>0){
if(b&1) ans=ans*a%mod;
b>>=1; a=a*a%mod;
} return ans;
}
ll solve(){
ll a,b,c,d,x,y;
sc(a); sc(b); sc(c); sc(d); sc(x); sc(y);
if(!b||!d) return pf("1\n");
if(!a) a++; if(!c) c++;
if(b-a>d-c) swap(a,c),swap(b,d),swap(x,y);
vector<pii>vv1,vv2; ll xx=x,yy=y;
for(ll i=2;1ll*i*i<=xx;++i){
while(xx%i==0) mp1[i]++,xx/=i;
} if(xx>1) mp1[xx]++;
for(ll i=2;1ll*i*i<=yy;++i){
while(yy%i==0) mp2[i]++,yy/=i;
} if(yy>1) mp2[yy]++;
for(auto t:mp1){
ll tt=t.first;
if(!mp2.count(tt)) continue;
vv1.push_back(pii(t.first,t.second));
}
for(auto t:mp2){
ll tt=t.first;
if(!mp1.count(tt)) continue;
vv2.push_back(pii(t.first,t.second));
}
// any vv1 fr == vv2 fr
ll ans=1; rep(i,0,vv1.size()){
ll t=vv1[i].first;
__int128 cnt=0; rep(j,a,b+1){
ll u=vv1[i].second*j,v=vv2[i].second;
// <=
ll num=min(u/v,d)-c+1;
if(num<0) num=0;
// getsum
if(num) cnt+=1ll*num*(num-1)/2*v+1ll*num*v*c;
// >
num=(d-c+1)-num;
if(num<0) num=0;
cnt+=1ll*u*num;
} ans=1ll*ans*qpow(t,cnt)%mod;
} return pf("%lld\n",ans);
}
signed main(){
/* ll _; sc(_); while(_--) */ solve();
}

I-The Crime-solving Plan of Groundhog

题意

给定 $n$ 个数,问重新排列成两个没有前导零的正整数的乘积最大值是多少。

思路

$sort$ 一下最小的一位乘上后面剩下的。有 $0$ 的时候要把 $0$ 往后移。虽然是乘法但其中一个乘数最多为 $9$ ,直接用大数加法的板子就可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
char s[maxn],q[maxn];
int th[maxn],ss;
void add(char *a,char *b){
mst(th,0); int ans=0;
int len1=strlen(a+1),len2=strlen(b+1);
int k=ss=1; while(len1||len2||ans){
if(len1>0) ans+=a[len1--]-'0';
if(len2>0) ans+=b[len2--]-'0';
th[ss++]=ans%10; ans/=10;
} while(!th[ss]) ss--;
}
int solve(){
int n; sc(n); getchar();
mst(s,0); rep(i,1,n+1){
char c=getchar(); s[i]=c; getchar();
} sort(s+1,s+n+1);
int ff(0); rep(i,1,n+1){
if(s[i]=='0') ff++;
else{
if(ff) swap(s[1],s[i]),swap(s[2],s[i+1]);
break;
}
} mst(q,0); rep(i,1,s[1]-'0'+1){
add(q,s+1); int cnt(0);
for(;ss>=1;ss--) q[++cnt]=th[ss]+'0';
} return pf("%s\n",q+1);
}
int main(){
int _; sc(_); while(_--) solve();
}