2018ICPC焦作
A-Xu Xiake in Henan Province
简单的输入输出模拟
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int n;
int a,b,c,d;
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
int cnt=0;
if(a>0)cnt++;
if(b>0)cnt++;
if(c>0)cnt++;
if(d>0)cnt++;
if(cnt==0)
printf("Typically Otaku\n");
else if(cnt==1)
printf("Eye-opener\n");
else if(cnt==2)
printf("Young Traveller\n");
else if(cnt==3)
printf("Excellent Traveller\n");
else
printf("Contemporary Xu Xiake\n");
}
}
B-Ultraman vs. Aodzilla and Bodzilla
C-Supreme Command
D-Keiichi Tsuchiya the Drift King
题意：
已知小圆半径r，小圆两个最两边半径的夹角d，车的宽和长分别为a,b，与直道与圆相切,要求小车从从外面往园内开的时候右上角要与小圆相切，问：路的宽度至少为多少时车才不会开出马路。
这题最主要的是画图，主要是图清楚了，式子也就出来了。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
const double PI=acos(-1);
int t,a,b,r,d;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&a,&b,&r,&d);
double fi=asin((a+r)/sqrt((a+r)*(a+r)+b*b));
double th=d*PI/180.0;
double res=sqrt((a+r)*(a+r)+b*b);
if(fi<=PI/2.0&&fi+th>=PI/2.0)
res-=r;
else
res=res*max(sin(fi),sin(fi+th))-r;
printf("%.12f\n",res);
}
}
E-Resistors in Parallel
题意：
多组样例，已知电阻的个数为n，让你求一堆电阻并联后电阻的阻值最小为多少。
以下公式题目已经给出：
并联电阻求阻值
对于每个电阻R的阻值的设定
对于一个集合i中存在电阻j的要求
solution
JAVA大数模拟+部分数学
先将电阻的求解转换为如下公式
对于下面这个式子，我的理解就是如果i=1，那么R1=1，其余情况则是在一堆素数里选择任意个素数连乘（每个素数只能选择一次）
因为要得到合并后的电阻尽可能小，那么我们就可以贪心的得到最大的电阻Rk为从2开始连续个素数相乘不超过n，因为Rk是阻值最大且满足条件的一个电阻，所以我们可以知道其余比Rk小的电阻的阻值就是从Rk中一堆连乘的素数中挑一些来相乘后得到的值。
那么R的分母就是一堆素数去或者不取进行dp求和就可以了
dp[i]=dp[i-1]*p[i]+dp[i-1]
import java.math.BigInteger;
import java.util.Scanner;
import java.util.Stack;
public class Main{
static BigInteger sum;
static int k;
static int[] prime=new int[1000006];
static BigInteger x;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int t=in.nextInt();
int cnt=0;
int[] vis= new int[1000006];
for(int i=2;i<=100000;i++) {
if(vis[i]==0) {
prime[cnt++]=i;
for(int j=i;j<=100000;j+=i) {
vis[j]=1;
}
}
}
while(t>0) {
BigInteger n=in.nextBigInteger();
x=BigInteger.valueOf(1);
if(n.compareTo(BigInteger.valueOf(1))==0) {
System.out.println("1/1");
t--;
continue;
}
k=-1;
for(int i=0;i<cnt;i++) {
if(x.multiply(BigInteger.valueOf(prime[i])).compareTo(n)<=0) {
x=x.multiply(BigInteger.valueOf(prime[i]));
k=i;
}else {
break;
}
}
sum=BigInteger.valueOf(1);
for(int i=0;i<=k;i++)
sum=sum.multiply(BigInteger.valueOf(prime[i]+1));
BigInteger z=sum.gcd(x);
System.out.println(x.divide(z)+"/"+sum.divide(z));
t--;
}
}
}
F-Honeycomb
这题就是一般的宽度优先遍历，只不过坐标有点麻烦。
但是我RE了好多次，因为漏打了个括号（所以敲代码的时候一定要仔细！！！！！！）
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
char tu[8005][8005];
int n,r,c;
int cnt[80005];
int sx,sy,tx,ty;
int dx[]={
1,-1,1,-1,2,-2},dy[]={
3,3,-3,-3,0,0};
int bfs()
{
map<P,int> d;
d[P(sx,sy)]=1;
queue<P> q;
q.push(P(sx,sy));
while(!q.empty())
{
P p=q.front();q.pop();
int now=d[P(p.first,p.second)];
for(int i=0;i<6;i++)
{
int xx=p.first+dx[i],yy=p.second+dy[i];
if(xx<0||xx>=4*r+3||yy<0||yy>=cnt[xx])continue;
if(tu[xx][yy]!=' ')continue;//cout<<xx<<' '<<yy<<endl;
xx+=dx[i],yy+=dy[i];
if(xx<0||xx>=4*r+3||yy<0||yy>=cnt[xx])continue;
if(d[P(xx,yy)]!=0)continue;
d[P(xx,yy)]=now+1;
q.push(P(xx,yy));
}
}
if(d[P(tx,ty)]==0)return -1;
else return d[P(tx,ty)];
}
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&r,&c);getchar();
for(int i=0;i<4*r+3;i++)
{
gets(tu[i]);
cnt[i]=strlen(tu[i]);
for(int j=0;j<6*c+3;j++)
{
if(tu[i][j]=='S')sx=i,sy=j;
if(tu[i][j]=='T')tx=i,ty=j;
}
}
printf("%d\n",bfs());
}
}
G-Shortest Paths on Random Forests
H-Can You Solve the Harder Problem?
I-Distance
题意：
多组样例，给了你n个点，n-1个相邻两点之间的距离，选的点的个数从1到n，求选i个点的任意两点距离之和的最大值是多少
solution：
轮流从两边选取点，从最外层开始。在这种情况下贪心是最优的。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
const double PI=acos(-1);
int n;
ll a[100005];
ll res[100005];
ll sum[100005];
int t;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
res[1]=0;
int cnt=0;
ll pre=0;
for(int i=2;i<=n;i++)
{
res[i]=res[i-1]+sum[n-cnt-1]-sum[cnt]+pre;
if(i%2){
pre+=sum[n-cnt-1]-sum[cnt];cnt++;}
}
printf("%lld",res[0]);
for(int i=2;i<=n;i++)
printf(" %lld",res[i]);
printf("\n");
}
}
京公网安备 11010502036488号