第一次啊，補題，希望大佬批評。
題目按我補題順序來的。
https://www.nowcoder.com/acm/contest/135#question
H? 題
最大公倍數
題意:給出兩個數，求最大公倍數
歐幾里德算法算出最大公約數k;
然后算出。最大公倍數即可
代碼如下：
#include<iostream>
#define ll long long
using namespace std;
ll gcd(ll a, ll b)
{
?return b == 0 ? a: gcd(b, a%b);
}
int main()
{
?ll n, m;
?cin >> n >> m;
?ll kk = gcd(n, m);
?cout << (n / kk)*(m / kk)*kk << endl;
?return 0;
}
?
J 題? time?
題意：
給出一個時間，比如23：32，得出不是它本生的上一個和下一個回文時間，（回文時間指的是：ab：ba這種格式）
思路一：
模擬：直接一分一分的減去，得到下一個回文時間，一分一分的加得到上一個時間。不過，要仔細些不然會在這里出錯。 ? ? ? ? ? ? ? ? ? ? ? ?? 然后，寫一個回文的判斷就可以了。
代碼如下：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
?int a, b,h,m;
?scanf("%d:%d", &a, &b);
?//上一個時刻
?h = a;?m = b-1;
?while (1)
?{
??if (h == ((m % 10) * 10 + m / 10))
??{
???cout << h << ":" << m<<endl;
???break;
??}
??m--;
??if (m < 0)
??{
???m += 60;?h--;?if (h < 0)h += 24;
??}
?}
?h = a;?m = b+1;
?while (1)
?{
??if (h == ((m % 10) * 10 + m / 10))
??{
???cout << h << ":" << m<<endl;
???break;
??}
??m++;
??if (m >= 60)
??{
???m -= 60;?h++;?if (h >= 24)h -= 24;
??}
?}
}
思路二：
打表
因為：回文時鐘的種數只有16種（注意：06：60不符合）所以可以建一個結構體存下小時h和分m和總的分h*60+m；注意一下0：0是24*60所以注意一下就可以了，直接把所給的時間在這個數組中找一下第一個比它大的就行（注意：0：0）
代碼略
?
I? 題
題意：
給你一個數組存入數字，然后又n次操作，每次對 l 到 r 區域進行每個數字加或減去d。然后，輸出x到y區域的所有數字之和。
思路：
例子：
建一個數組記錄操作數sum[ ]只操作一次：從4到6加7，則sum[4] + =7;sum[6+1] - =7;? 然后就for (int i = 1; i <= n; i++) ?? sum[i] += sum[i - 1];? 是不是在4到6之間，sum都是7了
如果是4到6減去7， 則sum[4] - = -7;sum[6+1] + =7;然后就for (int i = 1; i <= n; i++) ?? sum[i] += sum[i - 1];? 是不是在4到6之間，sum都是? -7 了.
那么多組操作呢？
先把這段代碼放上來；
while (m--)
?{
??scanf("%d%d%d%d", &a, &b, &c, &d);
??if (a == 0) sum[b] += d, sum[c + 1] -= d;
??else sum[b] -= d, sum[c + 1] += d;
?}
?for (int i = 1; i <= n; i++)
??sum[i] += sum[i - 1];
是不是擔心，這樣會出錯。其實不用的。剛剛一次操作是 ?sum[4] + =7;sum[6+1] - =7或則 ?sum[4] - = -7;sum[6+1] + =7? 多組操作會影響每一組操作的獨立性嗎？ 答案是不會。你可以把它看做是這樣的代碼；
for (int i = 0; i < t; i++)
{
?scanf("%d%d%d%d", &a, &b, &c, &d);
?if (a == 0) sum[i][b] += d, sum[i][c + 1] -= d;
?else sum[i][b] -= d, sum[i][c + 1] += d;
?for (int j = 1; j <= n; j++)
??sum[i][j] += sum[i][j - 1];
}
for (int i = 1; j <= n;j++)
for (int j = 0; j < t; j++)
{
?num[j] += sum[j][i];
}
但是，每一次的操作是獨立的（相當于數學中數據等價一樣），所以，就把多組操作一起處理了。
代碼如下：
?
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll num[1000004], sum[1000004];
ll ans = 0;
int main()
{
?int n, m, a,b,c,d, x,y;
?scanf("%d%d", &n, &m);
?for (int i = 1; i <= n; i++)
??scanf("%lld", &num[i]);
?while (m--)
?{
??scanf("%d%d%d%d", &a, &b, &c, &d);
??if (a == 0) sum[b] += d, sum[c + 1] -= d;
??else sum[b] -= d, sum[c + 1] += d;
?}
?for (int i = 1; i <= n; i++)
??sum[i] += sum[i - 1];
?scanf("%d%d", &x, &y);
?for (int i = x; i <= y; i++)
??ans += sum[i]+num[i];
?cout << ans << endl;
}
?
?
F? 題
這個題讓我想起了各種切割（數學）
總結一下：
n條直線最多分平面問題
n(n+1)/2+1;
折線分平面
2*n^2-n+1;
封閉曲線分平面
n^2-n+2;
平面分割空間
(n^3+5n)/6+1;
N個三角形分割平面
3*n^2-3*n+2
在一個圓上有n個點，將n個點兩兩相連分割圓
1 + n*(n - 1) / 2 + n*(n - 1)*(n - 2)*(n - 3) / 24
具體證明就不說了，（線段和射線決定對應一個區域（特別的復雜的都是遞推了））
題意：就不用說了
思路：直接套數學公式
代碼如下：
#include<iostream>
#define ll long long
using namespace std;
int main()
{
?ll n;
?while (cin >> n)
?{
??cout << 1 + n*(n - 1) / 2 + n*(n - 1)*(n - 2)*(n - 3) / 24 << endl;
?}
?return 0;
}
?
A? 題 ? ?? 無關
題意：給你一個集合，集合中元素都是素數（其實只要兩兩互質就行）,問你在一個從? l 到 r 范圍中，有幾個數不被集合中的任何一個元素整除，（不是，他們的倍數）.
思路：
找到他們倍數的個數n就可以了，（正難則反（高中））則答案為 （r-l+1）-n;
那么，直接變成在 1到 l和1 到 r的個數，再相減，就是最后答案了。
額，如何找1? 到 L 的個數呢？
L/a就等于a在1到L的倍數的個數了
那么怎么找既是a又是b的倍數呢？直接 L/(a*b)；注意：L/(a*b)=>L/a / b;也就是說，可以在不同時刻來除，不影響結果的。
這樣就可以找集合中各個元素的倍數個數n1， 兩個元素乘積的倍數n2, 三個......n3,? 四個，，，，，n4
然后用概率論中的概率公式? s=f(a)+f(b)+f(c)+......(-1)^(n-1)(f(n));（隨機時間概率公式，我打了大概的樣子）
中間：因為肯定要用到集合所形成的子集的枚舉：怎么枚舉呢？
比如：假如有3個元素{a,b,c}那么有八個子集（子集個數公式2^n, 非空子集和真子集公式2^n-1,非空真子集2^n-2）:
{},{a}, {b}, {c},{a,b},{a,c}, {b,c}, {a,b,c};? 元素個數為3
000 {}
001 { , ,a}
010 { ,b, }
100 {c, , }
011 { ,b ,a}
101 ......
110 ......
111 {c, b, a}
這樣不就可以表示成 0——7,?
好了，
代碼是怎樣,不多說
f? 用來表示（-1）^(n-1)
1<<n（n是元素個數）表示子集個數,怎樣把每個子集表示一遍。
for (ll i = 1; i < (1 << n); i++)
?{
??temp = m;?f = -1;
??for (int j = 0; j < n; j++)
??{
???if ((i >> j) & 1==1)
???{
????temp /= a[j];
????f *= -1;
???}
??}
??res += temp*f;
?}
?
總的代碼如下：
#include<iostream>
#include<stdio.h>
#define ll long long
using namespace std;
ll a[105];
ll l, r, n;
ll ans(ll m)
{
?ll res = 0;
?ll f, temp;
?for (ll i = 1; i < (1 << n); i++)
?{
??temp = m;?f = -1;
??for (int j = 0; j < n; j++)
??{
???if ((i >> j) & 1==1)
???{
????temp /= a[j];
????f *= -1;
???}
??}
??res += temp*f;
?}
?return m-res;
}
int main()
{
?scanf("%lld%lld%lld", &l, &r, &n);
?for (int i = 0; i < n; i++)
?scanf("%lld", &a[i]);
?ll res = ans(r) - ans(l-1);
?printf("%lld\n", res);
}
專門講集合子集的博客
https://blog.csdn.net/yzl20092856/article/details/39995085
?
D 題
這不是我重點的題目：
注意一下優化就可以了，本質是用到? 一個階乘中有幾個5，有多少個5就有多少個0
代碼如下：
#include<iostream>
using namespace std;
long long f(long long n){
?long long sum = 0;
?while (n){
??sum += n / 5;
??n /= 5;
?}
?return sum;
}
int main(){
?long long n;
?long long sum = 0;
?cin >> n;
?for (int i = 5; i <= n; i++){
??if (i + 5 <= n){
???sum += 5 * f(i);
???i += 4;
??}
??else{
???sum += f(i)*(n - i + 1);
???i = n;
??}
?}
?cout << sum;
?return 0;
}
?
emmmmm,這道題，有點神，讀題。大佬讀題都是說小魚吃大魚，維護了平衡。我讀的是坐一天月子不吃東西。。。反正，都是看代碼猜題意：
也就是，每過2天，有一天不能吃東西
就是n-n/3;
代碼如下：
#include<stdio.h>
#define ll long long
int main()
{
?ll n;
?while (scanf("%lld", &n)!=EOF)
?{
??printf("%lld\n", n - n / 3);
?}
}
?
