題目鏈接
A 寒假集訓(差分、結構體排序)
思路
- 題目總共給了 n+m 個人,n 個已經進入作業室,m 個人是未進入的,
- 之后又 k 場比賽,每場比賽都會對一些區間的內的人進行加分,由于區間數量比較多肯定不可以暴力,所以要用差分維護區加法,
- k 場比賽之后,讓我輸出前 n 名的排名 id,這明顯是結構體 sort 排序一下就行了,
- 具體看代碼,,,,
#include<bits/stdc++.h>
using namespace std;
const int mxn = 200005;
struct Node
{
long long id, score;
} ar[mxn];
bool cmp(Node a, Node b)
{
if(a.score == b.score)
return a.id < b.id;
return a.score > b.score;
}
int main()
{
int T; scanf("%d", &T);
while(T --)
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
int t = n + m; //總人數
for (int i = 1; i <= t; i ++) //初始化
{
ar[i].id = i;
ar[i].score = 0;
}
while(k --)
{
int p, s; scanf("%d %d", &p, &s);
while(p --)
{
int l, r;
scanf("%d %d", &l, &r);
ar[l].score += s; //進行差分
ar[r + 1].score -= s;
}
}
for (int i = 1; i <= t; i ++) //求前綴和的得到每一個位置的加分過后之后的值
{
ar[i].score += ar[i - 1].score;
}
sort(ar + 1, ar + 1 + t, cmp);
int num = 0;
for (int i = 1; i <= n; i ++) //在前 n 名內找一下符合題意的數量
{
if(ar[i].id > n)
num ++;
printf("%lld\n", ar[i].id);
}
printf("%d\n\n", num);
}
return 0;
}
B最近比賽太難了 來道水題
思路
- 題目讓求兩場比賽的總分第 100 名的分數最少為多少?
- 這題越想越繞,其實就兩句話,
- 第一句:兩場比賽的 第 100 名的最低分至少是(a+b),
- 第二句:兩場比賽的 第 100 名的最低分至少是 (c+d),
- 明顯只能選擇的 (a+b) 與(c+d) 大的那個數,因為大的那個數限制小的那個數的取值范圍,
代碼
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a, b, c, d;
scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
long long ans = max(a + b, c + d);
printf("%lld\n", ans);
return 0;
}
最近比賽太水了 來道難題
思路
- 暴力做就行了
代碼
#include<bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 10;
int ar[mxn];
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &ar[i]);
}
sort(ar + 1, ar + 1 + n);
for (int i = 100; ; i --)
{
int t = sqrt(ar[i]);
if(t * t != ar[i])
{
printf("%d\n", ar[i]);
break;
}
}
return 0;
}
這仗還打不打!!!!(貪心)
思路
- 這題是個貪心題,
- 首先 cxs 給每個學生講任務的總時間是恒定的,
- 只不過給學生講任務的順序,造成學生做任務的起始時間不同,
- 要想讓總時間盡肯能的少,就要的先給那些做任務耗時長的學生講,那么他們就可以利用到更多的使用到 cxs 給其他學生講任務的間隔,他們的任務就更可能在 cxs 給所有的學生講完任務之前把任務完成,這樣就可能使耗時更少
代碼
#include<bits/stdc++.h>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
using namespace std;
const int mxn = 1e5 + 10;
struct Node
{
int a, b;
} ar[mxn];
bool cmp(Node x, Node y)
{
return x.b > y.b;
}
int main()
{
Run();
int n, cas = 1;
while(scanf("%d", &n) && n)
{
for (int i = 1; i <= n; i ++)
{
scanf("%d %d", &ar[i].a, &ar[i].b);
}
sort(ar + 1, ar + 1 + n, cmp);
int t = 0, now = 0;
for (int i = 1; i <= n; i ++)
{
now += ar[i].a;
t = max(t, now + ar[i].b);
}
printf("Case %d: %d\n", cas ++, t);
}
return 0;
}
It is water
- 規律題,分情況討論一下就行了
思路
代碼
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long T; scanf("%lld", &T);
while(T --)
{
long long n, m;
scanf("%lld %lld", &n, &m);
long long ans;
if(n == 1)
{
ans = 0;
}
else if(n == 2)
{
ans = m;
}
else
{
ans = 2 * m;
}
printf("%lld\n", ans);
}
return 0;
}
這題不會有坑吧(簡單貪心)
思路
- 第一種菜只能用碗,而第二種菜既可以用碗又可以用盤子,
- 哪我們的貪心思路就是,遇見第一中的菜的時候只能使用碗(碗的數量 - 1),如果碗不夠就要的洗一個碗了(清洗數量 + 1),
- 如果遇見第二種菜,我們盡量先用盤子,盤子用完了在用碗,碗用完了 那就沒辦法了,只能 清洗次數 + 1
代碼
#include<bits/stdc++.h>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
using namespace std;
const int mxn = 1e5 + 10;
int main()
{
Run();
int n, a, b, t, ans = 0;
scanf("%d %d %d", &n, &a, &b);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &t);
if(t == 1)
{
if(a > 0)
{
a --;
}
else
{
ans ++;
}
}
else
{
if(b > 0)
{
b --;
}
else if(a > 0)
{
a --;
}
else
{
ans ++;
}
}
}
printf("%d\n", ans);
return 0;
}
聽聽,這說的是人話嘛?
思路
- 題目問我們能否在給的數字串中選擇兩個相同的子串,
- 其實我們只要能選兩個長度為 1 的相同子串就行了,
- 其實轉化一下就是求是否存在某個數字出現兩個,
- 由于資料范圍比較小,直接暴力判斷就行了
代碼
#include<bits/stdc++.h>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
using namespace std;
const int mxn = 1e5 + 10;
int ar[mxn];
int main()
{
int t; scanf("%d", &t);
while(t --)
{
int n, flag = 0; scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &ar[i]);
for (int j = 1; j < i; j ++)
{
if(ar[i] == ar[j])
{
flag = 1;
break;
}
}
}
printf("%s\n", flag ? "Yes" : "No");
}
return 0;
}
帶可莉出去玩~(后綴和+貪心)
思路
- 首先如果如果無法使用傳送的話,那么只能從乖乖的從地點 1 走到 n,
- 因為有了傳送,首先明確我們傳送只能向著 n 所的在的那個方向傳送,而且能穿多遠就盡量傳多遠,傳送的兩個城市之間的路程耗時為 0,那么的選擇傳送地點的時候肯定是選的傳送路程比較的大的那個城市進行傳送,
- 至于怎么的找傳送路程比較大的那個路程,用后綴和維護任意兩個城市的直接的距離,列舉的列舉起點城市,維護一個距離最大值 mx 就行了,
- 答案就是總距離 sum-mx,
- 最后別忘了特殊討論傳送距離 k>=n 的情況,這個時候耗時為 0
代碼
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <string>
#include <map>
#include <bitset>
#include <vector>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define db double
#define ll long long
#define ull unsigned long long
#define Pir pair<ll, ll>
#define m_p make_pair
#define for_(i, s, e) for(ll i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(ll i = (ll)(e); i >= (ll)(s); i --)
#define memset(a, b, c) memset(a, (int)b, c);
#define size() size() * 1LL
#define sc scanf
#define pr printf
#define sd(a) scanf("%lld", &a)
#define ss(a) scanf("%s", a)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define esp 1e-7
#define mod (ll)(1e9 + 7)
using namespace std;
/*=========================ACMer===========================*/
const int mxn = 1e6 + 10;
long long ar[mxn];
long long surfix[mxn];
int main()
{
long long n, k, sum = 0;
scanf("%lld %lld", &n, &k);
n --;
for (int i = 1; i <= n; i ++)
{
scanf("%lld", &ar[i]);
sum += ar[i];
}
if(k >= n) //進行一下特判,否則錯
{
printf("0\n");
return 0;
}
for (int i = n; i >= 1; i --) //求前綴和
{
ar[i] += ar[i + 1];
}
ll mx = 0;
for (int i = n - k + 1; i >= 1; i --)
{
mx = max(mx, ar[i] - ar[i + k]);
}
printf("%lld\n", sum - mx);
return 0;
}
A + B and A - B
思路
直接看代碼吧
代碼
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <string>
#include <map>
#include <bitset>
#include <vector>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define db double
#define ll long long long
#define ull unsigned long long
#define Pir pair<long long, long long>
#define m_p make_pair
#define for_(i, s, e) for(long long i = (long long)(s); i <= (long long)(e); i ++)
#define rep_(i, e, s) for(long long i = (long long)(e); i >= (long long)(s); i --)
#define memset(a, b, c) memset(a, (int)b, c);
#define size() size() * 1LL
#define scanf scanf
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define esp 1e-7
#define mod (long long)(1e9 + 7)
using namespace std;
/*=========================ACMer===========================*/
const long long mxn = 2e5;
char f, a[mxn], b[mxn];
long long ar[mxn], br[mxn], cr[mxn];
void add(long long ar[], long long br[], long long la, long long lb)
{
long long ln = max(la, lb);
long long sur = 0;
for (int i = 0; i <= ln; i ++)
{
cr[i] = (ar[i] + br[i] + sur) % 10;
sur = (ar[i] + br[i] + sur) / 10;
}
long long x = ln;
while(x && cr[x] == 0) x --;
for (int i = x; i >= 0; i --) printf("%lld", cr[i]);
printf("\n");
}
bool cmp(long long ar[], long long br[], long long la, long long lb)
{
if(la > lb) return 1;
if(la < lb) return 0;
for (int i = la - 1; i >= 0; i --)
{
if(ar[i] < br[i]) return 0;
}
return 1;
}
void subtract(long long ar[], long long br[], long long la, long long lb)
{
long long ln = max(la, lb);
long long sub = 0;
for (int i = 0; i <= ln; i ++)
{
cr[i] = ar[i] - br[i] - sub;
if(cr[i] < 0)
sub = 1, cr[i] += 10;
else
sub = 0;
}
long long x = ln;
while(x && cr[x] == 0) x --;
for (int i = x; i >= 0; i --) printf("%lld", cr[i]);
printf("\n");
}
void init()
{
memset(ar, 0, sizeof ar);
memset(br, 0, sizeof br);
memset(cr, 0, sizeof cr);
}
int main()
{
long long T, cas = 1; scanf("%lld", &T);
while(T --)
{
getchar();
init();
scanf("%c %s %s", &f, a, b);
long long la = strlen(a);
long long lb = strlen(b);
reverse(a, a + la);
reverse(b, b + lb);
for (int i = 0; i < la; i ++) ar[i] = a[i] - '0';
for (int i = 0; i < lb; i ++) br[i] = b[i] - '0';
if(f == '+')
{
printf("Case %lld:加法\n", cas ++);
add(ar, br, la, lb);
}
else
{
printf("Case %lld:減法\n", cas ++);
if(cmp(ar, br, la, lb))
{
subtract(ar, br, la, lb);
}
else
{
printf("-");
subtract(br, ar, lb, la);
}
}
}
return 0;
}
簡簡單單
思路
- 水題直接看代碼
代碼
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <string>
#include <map>
#include <bitset>
#include <vector>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define db double
#define ll long long
#define ull unsigned long long
#define Pir pair<ll, ll>
#define m_p make_pair
#define for_(i, s, e) for(ll i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(ll i = (ll)(e); i >= (ll)(s); i --)
#define memset(a, b, c) memset(a, (int)b, c);
#define size() size() * 1LL
#define sc scanf
#define pr printf
#define sd(a) scanf("%lld", &a)
#define ss(a) scanf("%s", a)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define esp 1e-7
#define mod (ll)(1e9 + 7)
using namespace std;
/*=========================ACMer===========================*/
const int mxn = 1e6 + 10;
long long ar[mxn];
long long surfix[mxn];
long long C(ll m)
{
return m * (m - 1) / 2;
}
int main()
{
long long n, m;
scanf("%lld %lld", &n, &m);
ll sum = 0;
sum += C(n);
sum += C(m);
printf("%lld\n", sum);
return 0;
}
看看,這說的是人話嘛?(模擬)
思路
- 這題首先由 1~1e9 每個點代表一個盒子,之后給了我們 m 個不相交區間段的描述 l,r,v,表示 [l, r] 的所有點的權值為 v;沒有區間描述過的點的權值默認為 0,當所有區間描述完之后,讓我選擇一個長度為 k 的子區間其區間權值和最大
- 這種題一看資料就知道沒法暴力列舉區間 1~1e9 中所有長度為 k 的子區間段,
- 首先我先對區間按左端點進行進行 sort 排序,
- 之后我們可以從前向后回圈先列舉所有的區間左端點 s,以 s 為開始長度為 k 的區間區間段,每次列舉都會產生一個最優值,
- 之后再從后向前回圈列舉所有區間的右端點假設為 e,以 e 為結尾的長度為 k 的子區間,每次繼續列舉都會產生一個最優值,
- 把所有答案的最優值維護一下 最優 就是答案了
代碼
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <string>
#include <map>
#include <bitset>
#include <vector>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
void Run(int x = 0) {
#ifdef ACM //宏定義免注釋 freopen
if(! x) fre(); else Fre();
#endif
}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define db double
#define ll long long
#define ull unsigned long long
#define Pir pair<ll, ll>
#define m_p make_pair
#define for_(i, s, e) for(ll i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(ll i = (ll)(e); i >= (ll)(s); i --)
#define memset(a, b, c) memset(a, (int)b, c);
#define size() size() * 1LL
#define sc scanf
#define pr printf
#define sd(a) scanf("%lld", &a)
#define ss(a) scanf("%s", a)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define esp 1e-7
#define mod (ll)(1e9 + 7)
using namespace std;
/*=========================ACMer===========================*/
const ll mxn = 2e6 + 10;
struct Seg
{
ll l, r, c;
} seg[mxn];
bool cmp(Seg a, Seg b)
{
return a.l < b.l;
}
int main()
{
Run();
ll T; scanf("%lld", &T);
while(T --)
{
ll n, k;
scanf("%lld %lld", &n, &k);
for (int i = 1; i <= n; i ++)
{
scanf("%lld %lld %lld", &seg[i].l, &seg[i].r, &seg[i].c);
}
sort(seg + 1, seg + 1 + n, cmp);
seg[0] = (Seg){ 0, 0, 0 };
seg[n + 1] = (Seg){ INF, INF, 0 };
ll cost = 0, start, end; //now 現在的所選擇的長度為 k 的區間的開始位置,end 為現在所選擇長度為 k 的區間的結束位置, p 上一次所選擇的區間的結束位置
ll sid = 0, eid = 1, ans = -INF; //sid 正在列舉區間的左端點所在的區間段下標位置;eid 為正在列舉區間的右端點的所在的區間段的下標
//正著列舉一遍維護最優值
for (int i = 1; i <= n; i ++)
{
start = seg[i].l;
end = start + k - 1;
cost -= seg[sid].c * (seg[sid].r - seg[sid].l + 1);
sid ++;
while(seg[eid].r <= end)
{
cost += seg[eid].c * (seg[eid].r - seg[eid].l + 1);
eid ++;
}
if(seg[eid].l <= end)
{
cost += seg[eid].c * (end - seg[eid].l + 1);
}
ans = max(ans, cost);
if(seg[eid].l <= end)
{
cost -= seg[eid].c * (end - seg[eid].l + 1);
}
}
seg[0] = (Seg){ -INF, -INF, 0 };
seg[n + 1] = (Seg){ 0, 0, 0 };
cost = 0, sid = n + 1, eid = n;
//倒著列舉一遍維護最優值
for (int i = n; i >= 1; i --)
{
start = seg[i].r;
end = start - k + 1;
cost -= seg[sid].c * (seg[sid].r - seg[sid].l + 1);
sid --;
while(seg[eid].l >= end)
{
cost += seg[eid].c * (seg[eid].r - seg[eid].l + 1);
eid --;
}
if(seg[eid].r >= end)
{
cost += seg[eid].c * (seg[eid].r - end + 1);
}
ans = max(ans, cost);
if(seg[eid].r >= end)
{
cost -= seg[eid].c * (seg[eid].r - end + 1);
}
}
printf("%lld\n", ans);
}
return 0;
}
聽取 Wa 聲一片
思路
- 這一題先用桶排的思想,統計一下每個數字出現的次數,
- 之后從小到大回圈輸出一個下,每個數 > 0 的數字,并且把這數字的數量 - 1,
- 如果還有的數字的次數 > 0 那么繼續回圈執行 2. 程序…
- 其實標程不是這樣的,因為有一些同學沒有學佇列 queue 原因,所以資料沒有有加強,因此沒把上面👆說的那種暴力思路給卡掉,
- 正確的程序,首先我們的正常分析上面的那種思路話,每個數的取值范圍是 0~1e6, 而且總的數字個數為 n<=1e6, 極端情況的話,當給的資料是 1e6 個 1e6 的話,由于 n 是 1e6 所以外出回圈要執行 1e6 次,對于每次外層回圈都要從 0~1e6 遍歷一遍,所有極端情況總共會運行 1e12 次,超出了 1 秒最多可已運行大概 1e8 次的,所以會超時,
- 耗時的主要出現在的了 回圈輸出的那一部分,因此我們可以用佇列把每個存在的數都壓入佇列,回圈輸出,當某數的次數為 0 的時候就不把它在壓入佇列了,這個樣對于 n 為 1e6 的時候,只需要執行 1e6 次就可把所有的數輸出出來了
暴力代碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e6+5;
typedef long long ll;
ll a[N],ak[N];
int main()
{
ll n,sum=0,maxa=-1e9;;
scanf("%lld",&n);
for(ll i=0; i<n; i++)
{
scanf("%lld",&a[i]);
if(maxa<a[i])
maxa=a[i];
ak[a[i]]++;
sum++;
}
//printf("%lld\n",sum);
while(sum)
{
for(ll i=0; i<=maxa; i++)
{
if(ak[i]>0)
{
printf("%lld ",i);
ak[i]--;
sum--;
}
}
}
return 0;
}
標準代碼
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
long long n, m, t;
long long fac[1000005];
queue<long long >p;
long long mp[1000005];
long long ar[1000005];
int main()
{
long long i,j;
scanf("%lld",&n);
long long x;
for(i=0;i<n;i++)
{
scanf("%lld",&ar[i]);
mp[ar[i]]++;
}
sort(ar,ar+n);
n=unique(ar,ar+n)-ar;
for(i=0;i<n;i++)
{
p.push(ar[i]);
}
long long q=0;
while(!p.empty())
{
x=p.front();
p.pop();
mp[x]--;
if(q==0)
{
q=1;
printf("%lld",x);
}
else
{
printf(" %lld",x);
}
if(mp[x]>=1)
{
p.push(x);
}
}
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/ruanti/234291.html
標籤:其他
上一篇:c語言實驗——G-鞍點計算
