8.08 体验极差的牛客9
A-Groundhog and 2-Power Representation
题意
给一个式子，每个括号前省略了一个 ^ 符号，问式子运算后的结果。
思路
卡语言是真的恶心，Python 一行就行，真的没意思，体验极差
倒着模拟记录状态，Java 写的
代码
代码语言：javascript复制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 快，就这
代码
代码语言：javascript复制#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("1n");
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("%lldn",ans);
}
signed main(){
/* ll _; sc(_); while(_--) */ solve();
}I-The Crime-solving Plan of Groundhog
题意
给定 n 个数，问重新排列成两个没有前导零的正整数的乘积最大值是多少。
思路
sort 一下最小的一位乘上后面剩下的。有 0 的时候要把 0 往后移。虽然是乘法但其中一个乘数最多为 9 ，直接用大数加法的板子就可以。
代码
代码语言：javascript复制#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; 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("%sn",q 1);
}
int main(){
int _; sc(_); while(_--) solve();
}
