2016 round A
A. Googol String
small && large
LL a[];
int dfs(LL pos, int id, bool f)
{
if(pos== || pos==a[id-]+)
return f? :;
if(pos>a[id-])
return dfs(a[id]-pos+, id-, f^);
else
return dfs(pos, id-, f);
}
int main()
{
freopen("A-small-practice.in", "r", stdin);
freopen("A.out", "w", stdout);
a[]=;
for(int i=;i<=;i++)
a[i]=a[i-]*+;
int t, ca=;
scanf("%d", &t);
while(t--)
{
LL n;
scanf("%I64d", &n);
int pos=lower_bound(a, a+, n)-a;
printf("Case #%d: %d\n", ca++, dfs(n, pos, ));
}
return ;
}
B. gCube
n个数，m个询问
每个询问给[l, r]
求 $\sqrt[^{r-l+1}]{\prod\limits_{i=l}^{r}a_i}$
smal
暴力二分，large TLE了 跑10min都没跑完，应该是大数乘太费时间
public class Main
{
static BigDecimal quick(BigDecimal a, BigInteger b)
{
BigDecimal ans=BigDecimal.ONE;
while(b.compareTo(BigInteger.ZERO)!=0)
{
if(b.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO)!=0)
ans=ans.multiply(a);
b=b.divide(BigInteger.valueOf(2));
a=a.multiply(a);
}
return ans;
}
static BigDecimal sqrt(BigDecimal x, int n)
{
BigDecimal l=BigDecimal.ZERO, r=x;
while(r.subtract(l).abs().compareTo(BigDecimal.valueOf(1e-10))>0)
{
BigDecimal m=(l.add(r)).divide(BigDecimal.valueOf(2));
BigDecimal cur=quick(m, BigInteger.valueOf(n));
cur=cur.subtract(x);
if(cur.abs().compareTo(BigDecimal.valueOf(1e-10))<0)
return m;
else if(cur.compareTo(BigDecimal.ZERO)<0)
l=m;
else
r=m;
}
return l;
}
public static void main(String[] args) throws FileNotFoundException
{
// InputReader in=new InputReader();
// PrintWriter out=new PrintWriter(System.out);
Scanner in=new Scanner(new File("B-large-practice.in"));
PrintWriter out = new PrintWriter(new File("B.out"));
int t=in.nextInt();
int ca=1;
while((t--)!=0)
{
int n=in.nextInt();
int m=in.nextInt();
int []a=new int[n];
for(int i=0;i<n;i++)
a[i]=in.nextInt();
BigDecimal []b=new BigDecimal[n];
b[0]=BigDecimal.valueOf(a[0]);
for(int i=1;i<n;i++)
b[i]=b[i-1].multiply(BigDecimal.valueOf(a[i]));
out.println("Case #"+ca+":");ca++;
while((m--)!=0)
{
int l=in.nextInt();
int r=in.nextInt();
BigDecimal pre=BigDecimal.ONE;
if(l!=0) pre=b[l-1];
BigDecimal s=b[r].divide(pre);
out.printf("%.9f", sqrt(s, r-l+1));
out.println("");
}
}
out.close();
}
}
large
求n次根号下的就是把ans除n次刚好除完
那就for l 到 r 每次都除一个ans 最后与1比较 判断是否除完就行了
const LD eps=1e-10; // eps<1e9了要long double！！！ int a[1005];
LD sqrtn(int x, int y)
{
LD l=1, r=a[y];
for(int i=x;i<=y;i++) // 数列不递增！！注意取最大值！
r=max(r, (LD)a[i]);
while(fabs(l-r)>eps)
{
LD mid=(l+r)/2.0;
LD cur=1.0;
for(int i=x;i<=y;i++)
cur*=a[i]/mid;
// 要注意这里不能fabs(cur-1)<eps了就结束 因为cur与1<eps了 不代表mid与ans的误差也小于eps了！！
if(cur>1)
l=mid;
else
r=mid;
}
return l;
}
int main()
{
freopen("B-large-practice.in", "r", stdin);
freopen("B.out", "w", stdout);
int t, ca=1;
scanf("%d", &t);
while(t--)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)
scanf("%d", &a[i]);
printf("Case #%d:\n", ca++);
while(m--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%.9Lf\n", sqrtn(l, r));
}
}
return 0;
}
2017 round A
A. Country Leader
给n个字符串 输出其中字母最多的字符串 字母一样多 输出字典序最小
神tm 空格only appear in Large！！ 挂了A large真是日了狗的心情
char s[];
bool vis[];
int main()
{
freopen("A-large-practice.in", "r", stdin);
freopen("A.out", "w", stdout);
int t, ca=;
scanf("%d", &t);
while(t--)
{
printf("Case #%d: ", ca++);
int n;
scanf("%d", &n);
getchar();
string ans="";
int maxn=;
for(int i=;i<n;i++)
{
gets(s);
string ss=s;
memset(vis, , sizeof(vis));
int num=;
int len=strlen(s);
for(int j=;j<len;j++)
if(s[j]!=' ' && !vis[s[j]])
num++, vis[s[j]]=;
if(num>maxn)
maxn=num, ans=s;
else if(num==maxn)
if(ss<ans)
ans=ss;
}
cout<<ans<<endl;
}
return ;
}
A
B. Rain
给n*m的方格，每个格子有高度，水满了会增加格子高度，输出增加的高度
每个格子会变成 上下左右 比它高的 最小高度
从最小的高度开始 看每格能否合法的变成这个高度
vector<int> v;
int mp[][];
bool vis[][];
int ans, n, m;
bool can(int x, int y, int val)
{
// int num=0;
if(!vis[x][y] && mp[x][y]==val)
{
if(x== || x==n- || y== || y==m-)
return false;
vis[x][y]=;
// num=1;
if(x>){
if(!can(x-, y, val)) return false;}
if(x<n-){
if(!can(x+, y, val)) return false;}
if(y>){
if(!can(x, y-, val)) return false;}
if(y<m-){
if(!can(x, y+, val)) return false;}
}
else if(mp[x][y]<val)
return false;
return true;
}
void dfs(int x, int y, int num)
{
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(vis[i][j])
ans+=num-mp[i][j], mp[i][j]=num, vis[i][j]=;
}
int main()
{
freopen("B-large.in", "r", stdin);
freopen("B.out", "w", stdout);
int t, ca=;
scanf("%d", &t);
while(t--)
{
printf("Case #%d: ", ca++);
scanf("%d%d", &n, &m);
v.clear();
for(int i=;i<n;i++)
for(int j=;j<m;j++)
scanf("%d", &mp[i][j]), v.push_back(mp[i][j]);
sort(v.begin(), v.end());
int d=unique(v.begin(), v.end())-v.begin();
if(d<)
{
puts("");
continue;
}
ans=;
for(int ii=;ii<d;ii++)
{
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
memset(vis, , sizeof(vis));
if(mp[i][j]<v[ii] && can(i, j, mp[i][j]))
{
dfs(i, j, v[ii]);
}
}
}
}
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++)
// printf("%d ", mp[i][j]);puts("");}
printf("%d\n", ans);
}
return ;
}
B
C. Jane's Flower Shop
给n个系数 求一元n次方程在-1到1之间的那个解，题目保证有且仅有一解
因为保证有且仅有一解，因此Left和Right两端一定为一正一负
根据正负二分就行
typedef long double LD;
const LD eps=1e-; int a[];
int n;
LD cal(LD r)
{
LD cur=, ans=;
for(int i=;i<=n;i++, cur*=(+r))
ans+=a[n-i]*cur;
return ans;
}
int main()
{
freopen("C-large.in", "r", stdin);
freopen("C.out", "w", stdout);
int t, ca=;
scanf("%d", &t);
while(t--)
{
printf("Case #%d: ", ca++);
scanf("%d", &n);
for(int i=;i<=n;i++)
scanf("%d", &a[i]);
a[]=-a[];
LD l=-, r=;
LD ll=cal(l), rr=cal(r);
while(fabs(l-r)>eps)
{
LD m=(r+l)*0.5;
LD mm=cal(m);
if(mm< && ll<)
l=m;
else if(mm< && rr<)
r=m;
else if(mm> && ll>)
l=m;
else if(mm> && rr>)
r=m;
else
l=m;
}
printf("%.12Lf\n", l);
}
return ;
}
C