【纪中受难记】——Day17:本来能AK

(标题妄想)。

95/0/0

第二题很水,后来花5分钟切了。


 

3503. 粉刷(paint) (Standard IO)

Time Limits: 1000 ms  Memory Limits: 131072 KB  Detailed Limits   Goto ProblemSet

 

Description

鸡腿想到了一个很高(sha)明(bi)的问题,墙可以看作一个N*M的矩阵,有一些格子是有污点的。现在鸡腿可以竖着刷一次,覆盖连续的最多C列,或者横着刷一次,覆盖连续的最多R行。现在鸡腿把墙上的情况告诉你,请你告诉鸡腿最少要刷多少次才能刷干净!
 

Input

第1行,输入俩正整数N,M。

第2到N+1行,每行一个长度为M的字符串,每个字符可能是’.’表示干净的,或者’X’表示这个格子有污点。

第N+2行,输入俩正整数表示R和C。

Output

输出一行一个整数,表示鸡腿最少要刷几次。
 

Sample Input

输入1:
1 9
XXXXXXXXX
2 3
输入2:

11 14
XXX..XXX..XXX.
.X..X....X...X
.X..X....X...X
.X..X....X...X
.X...XXX..XXX.
..............
...XX...XXX...
....X......X..
....X....XXX..
....X......X..
...XXX..XXX...
1 2

Sample Output

输出1:
1
输出2:
7

 

这道题数据很水,贪心+特判就过了。

 


 

3504. 运算符(calc) (Standard IO)

Time Limits: 1000 ms  Memory Limits: 131072 KB  Detailed Limits   Goto ProblemSet

 

Description

鸡腿想到了一个很高(sha)明(bi)的运算符,那就是’!’,没错就是感叹号。他给了如下的定义:

1、n!k = n!(k-1) * (n-1)!k (n> 0 and k > 0)

2、n!k = 1 (n = 0)

3、n!k = n (k = 0)

现在鸡腿告诉你n和k你能告诉他n!k的不同约数个数有多少个吗?只要对1,000,000,009取模就可以了哦!
 

Input

一行,输入两个正整数n,k。

Output

一行,输出一个整数表示答案。
 

Sample Input

输入1:
3 1
输入2:
100 2

Sample Output

输出1:
4
输出2:
321266186
 

Data Constraint

对于30%的数据0 <n ≤ 10, 0 <k ≤ 10;

对于100%的数据0 <n ≤ 1000, 0 <k ≤ 100。

【纪中受难记】——Day17:本来能AK

 

由唯一分解定理和约数个数公式可知,

【纪中受难记】——Day17:本来能AK

没了。

 


 

 

6290. 倾斜的线 
(File IO): input:slope.in output:slope.out

Time Limits: 1000 ms  Memory Limits: 131072 KB  Detailed Limits   Goto ProblemSet

 

Description

【纪中受难记】——Day17:本来能AK
 

Input

【纪中受难记】——Day17:本来能AK

Output

【纪中受难记】——Day17:本来能AK
 

Sample Input

6 15698 17433
112412868 636515040
122123982 526131695
58758943 343718480
447544052 640491230
162809501 315494932
870543506 895723090 
 

Sample Output

193409386/235911335
 
 

Data Constraint

【纪中受难记】——Day17:本来能AK

 

b组唯一值得写的题。

按点在给的斜率意义下的截距排序,比较相邻的点斜率与给定斜率差,暴力即可。

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef long double ldo;
 5 const ll N=2e5+10;
 6 ll n,P,Q,ans;
 7 long double k,delta;
 8 ll gcd(ll a,ll b){
 9     return b==0?a:gcd(b,a%b);
10 }
11 struct num{
12     ll son,mon;
13     long double xie(num a){
14         return (long double)(a.mon-mon)/(a.son-son);
15     }
16     long double jie(){
17         return (long double)mon-k*son;
18     }
19 }e[N];
20 bool cmp(num x1,num x2){
21     return x1.jie()<x2.jie();
22 }
23 int main(){
24     freopen("slope.in","r",stdin);
25     freopen("slope.out","w",stdout);
26     scanf("%lld%lld%lld",&n,&P,&Q);
27     k=(long double)P/Q;
28     delta=1e9;
29     for(ll i=1;i<=n;i++){
30         scanf("%lld%lld",&e[i].son,&e[i].mon);
31     }
32     sort(e+1,e+n+1,cmp);
33     for(ll i=1;i<n;i++){
34         ldo tmp=e[i].xie(e[i+1]);
35         if(abs(tmp-k)<delta){
36             delta=abs(tmp-k);
37             ans=i;
38         }
39     }
40     ll tp1=abs(e[ans+1].mon-e[ans].mon);
41     ll tp2=abs(e[ans+1].son-e[ans].son);
42     ll g=gcd(tp1,tp2);
43     ll a1=tp1/g;
44     ll a2=tp2/g;
45     printf("%lld/%lld",a1,a2);
46     return 0;
47 }

 


明天A组见。

 

上一篇:Day17 计算文件夹的大小、os模块、shtil模块、zipfile、tarfile


下一篇:day17