HDU重现赛之2019CCPC-江西省赛
2024-08-29 22:36:48
本人蒟蒻，5个小时过了5道，看到好几个大佬AK，%%%%%%%
http://acm.hdu.edu.cn/contests/contest_show.php?cid=868
先放大佬的题解（不是我写的。。同学给的），能理解多少就靠你们自己了，还是希望大家能从大佬的题解中有所收获
口胡题解：
A. Co-Tree：由目标函数提到的两两距离和，可想到，在树上找个点，使得它到其它点距离和最小。
B. Math：考虑每秒开始时 “avin 拿着 Robot 在 i 点” 的状态 到 “Avin 拿着 Robot 在 i+1 点” 状态，需要时间 的期望？⼀一个状态自己转移到自己怎么办？
C. Trap：在互质这个限制条件，容斥！那么考虑没有互质的限制怎么做？枚举两条边，第三条边方案数怎么 快速统计？
D. Wave：枚举两种不同的数，复杂度多少？
E. Packing：我们需要决策，能 DP 吗？能贪心吗？按什么优先级来决定发哪个缓冲区的货呢？
F. String：乘法原理。
G. Traffic：哪些等待时间不合法？
H. Rng：for，for 枚举右端点可以做啊！观察两个 for 的做法，变成一个 for 就 win 了。
I. Buget：最低位决定答案。
J. Worker：按比例分配。
K. Class：解方程。
详细题解：
有些符号粘不出来，放截图吧，望见谅
有兴趣可以看看我过的题目（太蒻了，有点不好意思）
下面是题目：
1011 Class
Problem Description
Avin has two integers a, b (1 ≤ a, b ≤ 1, 000).
Given x = a + b and y = a - b, can you calculate a*b?
Input
The first line contains two integers x, y.
Output
Print the result of a*b.
Sample Input
Sample Output
签到题，直接粘代码
#include <stdio.h>
#include <algorithm> using namespace std; int main()
{
int a,b,x,y;
scanf("%d %d",&x,&y);
a=(x+y)/;
b=(x-y)/;
printf("%d\n",a*b);
return ;
}
1006 String
Problem Description
Avin has a string. He would like to uniform-randomly select four characters (selecting the same character is allowed) from it. You are asked to calculate the probability of the four characters being ”avin” in order.
Input
The first line contains n (1 ≤ n ≤ 100), the length of the string. The second line contains the string. To simplify the problem, the characters of the string are from ’a’, ’v’, ’i’, ’n’.
Output
Print the reduced fraction (the greatest common divisor of the numerator and denominator is 1), representing the probability. If the answer is 0, you should output "0/1".
Sample Input
avin aaaa
Sample Output
/
/
暴力过的，十分暴力
#include <stdio.h>
#include <algorithm> using namespace std; int gcd(int a,int b)
{
if(b==)
return a;
else return gcd(b,a%b);
} int main()
{
int n;
while(~scanf("%d",&n))
{
getchar();
char str[];
for(int i=;i<=n;i++)
{
str[i]=getchar();
}
int tot=;
int sum=;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
for(int g=;g<=n;g++)
{
for(int k=;k<=n;k++)
{
tot++;
// if(i<j&&j<g&&g<k) //第一次wa的点，理解错题意了
// {
if(str[i]=='a'&&str[j]=='v'&&str[g]=='i'&&str[k]=='n')
sum++;
// }
}
}
}
}
if(sum!=)
{
int t=gcd(sum,tot);
// printf("sum=%d tot=%d t=%d\n",sum,tot,t);
printf("%d/%d\n",sum/t,tot/t);
}
else
printf("0/1\n");
}
return ;
}
1009 Budget
Problem Description
Avin’s company has many ongoing projects with different budgets. His company records the budgets using numbers rounded to 3 digits after the decimal place. However, the company is updating the system and all budgets will be rounded to 2 digits after the decimal place. For example, 1.004 will be rounded down
to 1.00 while 1.995 will be rounded up to 2.00. Avin wants to know the difference of the total budget caused by the update.
Input
The first line contains an integer n (1 ≤ n ≤ 1, 000). The second line contains n decimals, and the i-th decimal ai (0 ≤ ai ≤ 1e18) represents the budget of the i -th project. All decimals are rounded to 3 digits.
Output
Print the difference rounded to 3 digits..
Sample Input
1.001 0.999 1.001 0.999
Sample Output
-0.001
0.001
0.000
不管输入是不是三位小数了，我当做不是来写的，中间写的时候又有了新的想法，稍微改变了思路，所以29~35行有点乱，懒得改了，能过就直接交了
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std; int main()
{
int n;
while(~scanf("%d",&n))
{
char str[];
double sum=;
for(int i=;i<n;i++)
{
double tem=;
scanf("%s",str);
int len=strlen(str);
int flag=;
int t=;
for(int i=;i<len;i++)
{
if(flag)
{
tem+=(str[i]-'')*1.0/t;
t*=;
continue;
}
if(str[i]!='.')
{
str[i]='';
}
else
{
flag=; if(str[i+])
str[i+]='';
else
break;
if(str[i+])
str[i+]='';
else break;
i+=;
}
}
if(tem<0.005)
sum-=tem;
else
sum+=0.01-tem;
}
if(sum<)
{
printf("-");
sum=-sum;
}
printf("%.3lf\n",sum);
}
return ;
}
1010 Worker
Problem Description
Avin meets a rich customer today. He will earn 1 million dollars if he can solve a hard problem. There are n warehouses and m workers. Any worker in the i-th warehouse can handle ai orders per day. The customer wonders whether there exists one worker assignment method satisfying that every warehouse handles the same number of orders every day. Note that each worker should be assigned to exactly one warehouse and no worker is lazy when working.
Input
The first line contains two integers n (1 ≤ n ≤ 1, 000), m (1 ≤ m ≤ 1018). The second line contains n integers. The i-th integer ai (1 ≤ ai ≤ 10) represents one worker in the i-th warehouse can handle ai orders per day.
Output
If there is a feasible assignment method, print "Yes" in the first line. Then, in the second line, print n integers with the i-th integer representing the number of workers assigned to the i-th warehouse.
Otherwise, print "No" in one line. If there are multiple solutions, any solution is accepted.
Sample Input
Sample Output
Yes No
根据比例分配的问题，这个long long就很烦，一直在卡我，注意1018是1018，十分无语
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
typedef long long LL;
LL n,m; int gcd(LL a,LL b)
{
if(b==) return a;
else return gcd(b,a%b);
} int lcm(LL a,LL b)
{
return (a/gcd(a,b) )*b;
} int main()
{
while(~scanf("%lld %lld",&n,&m))
{
LL a[];
LL t[];
LL w[];
LL z=;
for(LL i=;i<=n;i++)
{
scanf("%lld",&a[i]);
z=lcm(max(z,a[i]),min(z,a[i]));
}
// printf("z=%lld\n",z);
LL sum=;
for(LL i=;i<=n;i++)
{
t[i]=z/a[i];
sum+=t[i];
// printf("t[%d]=%d,sum=%d\n",i,t[i],sum);
}
if(m%sum!=)
{
printf("No\n");
continue;
}
printf("Yes\n");
LL g=m/sum;
// printf("g=%d\n",g);
for(LL i=;i<=n;i++)
{
if(i==)
printf("%lld",t[i]*g);
else
printf(" %lld",t[i]*g);
}
printf("\n");
}
return ;
}
1007 Traffic
Problem Description
Avin is observing the cars at a crossroads. He finds that there are n cars running in the east-west direction with the i-th car passing the intersection at time ai . There are another m cars running in the north-south direction with the i-th car passing the intersection at time bi . If two cars passing the intersections at the same time, a traffic crash occurs. In order to achieve world peace and harmony, all the cars running in the north-south direction wait the same amount of integral time so that no two cars bump. You are asked the minimum waiting time.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 1, 000). The second line contains n distinct integers ai (1 ≤ ai ≤ 1, 000). The third line contains m distinct integers bi (1 ≤ bi ≤ 1, 000).
Output
Print a non-negative integer denoting the minimum waiting time.
Sample Input
Sample Output
这个刚开始有点不理解车是怎样个等法，后来见好多人都交了，我就按照我自己的理解去写了，直接AC了，真好，就是感觉这种等法太反人类了
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
int n,m; int main()
{
while(~scanf("%d %d",&n,&m))
{
int a[]={};
int b[]={};
for(int i=;i<n;i++)
{
int t;
scanf("%d",&t);
a[t]=;
}
for(int i=;i<m;i++)
{
int t;
scanf("%d",&t);
b[t]=;
}
int p=;
while()
{
int flag=;
for(int i=;i<;i++)
{
if(b[i])
{
if(a[i+p])
{
flag=;
break;
}
}
}
if(flag)
{
break;
}
p++;
}
printf("%d\n",p);
}
return ;
}
船新版本
int main()
{
while(~scanf("%d %d",&n,&m))
{
int a[]={};
int b[]={};
for(int i=;i<n;i++)
{
int t;
scanf("%d",&t);
a[t]=;
}
for(int i=;i<m;i++)
{
scanf("%d",&b[i]);
}
int p=;
for(int i=;i<m;i++)
{ if(a[b[i]+p])
{
p++;
i=-;
}
}
printf("%d\n",p);
}
return ;
}
除了AC的5题，我和队友还尝试了Wave和Rng。Wave懂题意了，但不会做，Rng很简单，有快200人过了没读懂题，只能猜、猜、猜、菜、菜、菜。。。。
最后说一句RNGNB！！！
最新文章
- 基于pcDuino-V2的无线视频智能小车 - pcduino上的网络编程
- 『TCP/IP详解——卷一：协议』读书笔记——12
- [No00001C]不想背单词患者的福音！-快来定制你的个性词包-不想记、记不牢，这可怎么办？
- Odoo 路线规则实现机制浅析
- Magento 自定义一个搜索功能
- Entity Framework Code First ---EF Power Tool MySql
- owncloud乱码问题
- Media Queries for Standard Devices
- Nlog 配置总结
- jmeter 控制器
- Xcode6无法用xib得问题解决方法
- UVa 324 - Factorial Frequencies
- JAVA课程设计-计算器（201521123028 李家俊）
- zoj3432 Find the Lost Sock 亦或的运用
- js——图片懒加载
- 一、ESP8266入门（基于LUA开发）
- C#中的委托（delegate）（个人整理）
- 接口自动化 基于python+Testlink+Jenkins实现的接口自动化测试框架
- AIX上解压缩.tar.Z, .tar.gz, .zip及.tgz
- Intelli系列代理部分报错：You have JVM property https.proxyHost set..