F. 麗娃河的狼人傳說
Time limit per test: 1.0 seconds
Time limit all tests: 1.0 seconds
Memory limit: 256 megabytes
Accept / Submit: 224 / 1759
麗娃河是華師大著名的風景線。但由于學校财政緊缺，麗娃河邊的路燈年久失修，一到晚上就會出現走在河邊要打着手電的情況，不僅非常不友善，而且影響安全：已經發生了大大小小的事故多起。
友善起見，麗娃河可以看成是從 1 到 n 的一條數軸。為了美觀，路燈隻能安裝在整數點上，每個整數點隻能安裝一盞路燈。經專業勘測，有 m
請問至少還要安裝多少路燈。
Input
第一行一個整數 T (1≤T≤300)，表示測試資料組數。
對于每組資料：
- 第一行三個整數 n,m,k (1≤n≤103,1≤m≤103,1≤k≤n)。
- 第二行 k
- 接下來 m 行表示限制條件。第 i 行三個整數 li,ri,ti 表示：第 i 個區間 [li,ri] 至少要安裝 ti 盞路燈 (1≤li≤ri≤n,1≤ti≤n)。
Output
對于每組資料，輸出
Case x: y
。其中 x 表示測試資料編号（從 1 開始），y 表示至少要安裝的路燈數目。如果無解，y 為 −1。
Examples
Input
3
5 1 3
1 3 5
2 3 2
5 2 3
1 3 5
2 3 2
3 5 3
5 2 3
1 3 5
2 3 2
4 5 1 Output
Case 1: 1
Case 2: 2
Case 3: 1 Note
因為今天不是滿月，是以狼人沒有出現。
思路：将區間的最右端從小到大進行排序，将路燈盡可能的放在最右邊，這樣如果區間有重疊就能最大限度的利用路燈
AC代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int loc[1010];
struct line
{
int start;
int end;
int num;
}lines[1010];
bool cmp(line a,line b)
{
return a.end < b.end;
}
int main()
{
int t;
scanf("%d",&t);
for (int x=1; x<=t; x++)
{
memset(loc,0,sizeof(loc));
int n,m,k,temp;
scanf("%d%d%d",&n,&m,&k);
for (int i=0; i<k; i++)
{
scanf("%d",&temp);
loc[temp] = 1;
}
bool flag = false;
for (int i=0; i<m; i++)
{
scanf("%d%d%d",&lines[i].start,&lines[i].end,&lines[i].num);
//要放的樹比空間還多，則輸出-1
if (lines[i].num > lines[i].end - lines[i].start + 1)
flag = true;
}
if (flag)
printf("Case %d: -1\n",x);
else
{
int total = 0;
sort(lines,lines+m,cmp);
for (int i=0; i<m; i++)
{
int sum = 0;
for (int j=lines[i].start; j<=lines[i].end; j++)
{
if (loc[j])
sum++;
}
int temp = lines[i].num - sum;
if (temp <= 0)
continue;
for (int j=lines[i].end; j>=lines[i].start; j--)
{
if (loc[j] == 0)
{
loc[j] = 1;
total++;
temp--;
}
if (temp == 0)
break;
}
}
printf("Case %d: %d\n",x,total);
}
}
return 0;
} E. 黑心啤酒廠
Time limit per test: 1.0 seconds
Time limit all tests: 1.0 seconds
Memory limit: 256 megabytes
Accept / Submit: 1184 / 4093
黑心啤酒廠為了讓大家買啤酒，會把一瓶酒設計成恰好能倒七杯。由于聚會時經常會有大家一起幹杯這樣的事情，幹杯之前又要給每個人都倒滿，是以來兩個人的時候，幹完三輪，恰好多一杯；三個人的時候，幹完兩輪，恰好多一杯；四個人的時候會多三杯。在上述情況下，為了踐行不浪費的原則，就會多買一瓶啤酒，再幹一輪。當然多買的啤酒可能又有多了……然後循環往複，喝了好多好多。直到啤酒剛剛好喝完為止。
現在啤酒廠把酒瓶設計成剛好能倒 x 杯，請依次求出有 2 人、3 人，一直到 n
Input
輸入隻有一行，兩個整數 x,n (1≤x≤109,2≤n≤105)。
Output
輸出 n−1 行，分别表示 2,3,…,n
Examples
Input
7 5 Output
2
3
4
5 思路：求出杯數x和人數n的最小公倍數，用最小公倍數除以杯數就能得到瓶數，即x*n/gcd(x,n)為最小公倍數 ,除以x為瓶數，即n/gcd(x,n)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int gcd(int a,int b)
{
return b == 0 ? a : gcd(b,a%b);
}
int main()
{
int x,n,sum;
cin >> x >> n;
for (int i=2; i<=n; i++)
{
sum = i / gcd(x,i);
printf("%d\n",sum);
}
return 0;
}