*1:簽到題-5
*2:區間并集
*3:特殊的01串
*4:公因數-2
*5:WSAD
*6:陣列的貢獻值
1:簽到題-5
描述
嘉庚學院開展了為期兩周的線上教學活動，其中出勤是一個很重要的指標，
每次有 n 個同學應該來參加線上課程，他們都有自己獨特的學號來進行簽到，
但總有一個同學睡過了頭也就是他沒有簽到，要接受爆照的處罰（獎勵），你能幫老師找出是誰這么幸運么？
輸入
只有一組案例，
第一行是一個正整數 n，表示本次課程應該有 n 個同學來參與，（2 <= n <= 1e5)
第二行是 n 個互不相同的正整數 xi，分別表示這 n 個同學獨特的學號，(1 <= xi <= 1e9)
第三行是 n - 1 個互不相同的正整數，表示老師給出的已經簽到的 n - 1 個同學的學號，(保證是這節課應該來的同學的學號）
輸出
輸出一個正整數，表示沒有簽到同學的學號，然后換行，
樣例輸入
4
2 3 4 8
8 3 4
樣例輸出
2
HINT
老師給出的學號和應簽到的學號都不一定有序，
來源
20-21(2)第0次線上賽
解：
1、（最簡單的）（來自大佬涂涂）第一次輸入的和-第二次輸入的和，
2、（來自IST大佬）map容器 key-value學號不重復>set>s. erase>輸出
（太難不細說）(俺不會-理直氣壯)
3、兩個一維陣列進行sort排序，第一個對不上號的就是沒到的（下面代碼），
#include<iostream>
#include<algorithm>
//algorithm-sort
using namespace std;
int main()
{
int n;
cin>>n;
int *a=new int[n]();
int *b=new int[n-1]();
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n-1);
for(int i=0;i<n-1;i++)
{
cin>>b[i];
}
sort(b,b+n-2);
bool sc=0;
for(int i=0;i<n-1;i++)
{
if(sc==0)
{
if(a[i]!=b[i])
{
cout<<a[i]<<endl;
sc=1;
break;
}
}
}
if(sc==0) cout<<a[n-1]<<endl;
delete []a;
delete []b;
return 0;
}
2:區間并集
描述
存在 n 個區間：a1、a2、…… 、an，
求 a1 ∪ a2 ∪ a3 ∪ …… ∪ an，
輸入
只有一組案例，
第一行正整數 n 表示區間的個數，(1 <= n <= 1e5)
然后是 n 行，每行包含兩個正整數 L 和 R，分別表示一個區間左右端點，即 [ L，R ]，(0 <= L <= R <= 1e10)
輸出
根據左端點的大小，從小到大輸出取并集后的每個區間，
每個區間的左端點和右端點之間用空格隔開，每次輸出以后都要換行，
樣例輸入
6
1 2
1 4
8 10
8 9
5 6
6 7
樣例輸出
1 4
5 7
8 10
HINT
[1，2] 區間和 [1，4] 區間取并集后變為 [1，4]
[5，6] 區間和 [6，7] 區間取并集后變為 [5，7]
[8，9] 區間和 [8，10] 區間取并集后變為 [8，10]
來源
20-21(2)第0次線上賽
解：
1、結構體存盤每一次輸入的L、R（左右端），然后sort排序，排序規則看compare，然后記錄第一個L、R為l、r，后面有L大于記錄的r時輸出存盤的l、r，存盤新的L、R，如果后面的L不大于記錄的r則合并合集，取倆合集（存盤的l、r和該次的L、R）中最小的左端為l和最大的右端為r，（下面代碼）
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
struct qj
{
ll L;
ll R;
};
qj s[100005];
bool compare(qj a,qj b)
{
if(a.L==b.L)
{
return a.R<b.R;
}
return a.L<b.L;
}
int main()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>s[i].L>>s[i].R;
}
//cout<<"opening"<<endl;
sort(s,s+n+1,compare);
ll l=0,r=0;
for(ll i=1;i<=n;i++)
{
if(i==1)
{
l=s[i].L;
r=s[i].R;
}
else
{
if(s[i].L>r)
{
cout<<l<<" "<<r<<endl;
l=s[i].L;
r=s[i].R;
}
else
{
if(s[i].R>r)
{
r=s[i].R;
}
}
}
}
cout<<l<<" "<<r<<endl;
return 0;
}
3:特殊的01串
描述
我們定義一個字串是特殊的01串：
1.空串是特殊的01串，
2.僅由字符 0 和 1 構成且任意兩個相鄰的字符不都為 1，
現在請你構造一個長度為 n 的特殊的01串，請問你可以構造多少個？
輸入
第一行是一個正整數 T 代表測驗案例的數量，（1 <= T <= 1e5)
每組案例是一個整數 n，代表構造字串的長度，（0 <= n <= 1e6)
輸出
針對每組案例，輸出你可以構造多少個，然后換行，
由于答案可能很大，所以你只需要輸出它對 998244353 取模以后的結果，
樣例輸入
1
3
樣例輸出
5
HINT
長度為 3 的特殊的01串可以是 100 010 001 101 000，
來源
20-21(2)第0次線上賽
解：
1、找規律，陣列存盤（下面代碼），
#include<iostream>
#include<cstring>
#define mod 998244353
using namespace std;
int ans[1000005];
int main()
{
memset(ans,0,sizeof(ans));
ans[0]=1;ans[1]=2;ans[2]=3;ans[3]=5;
for(int i=4;i<=1000005;i++)
{
ans[i]=(ans[i-1]+ans[i-2])%mod;
}
int T;
cin>>T;
for(int f=1;f<=T;f++)
{
int n;
cin>>n;
cout<<ans[n]<<endl;
}
return 0;
}
4:公因數-2
描述
有 n 個數字，求它們的公共質因數，
輸入
只有一組案例，
第一行是一個正整數 n 代表數字的個數，(1 <= n <= 1e5)
然后是 n 個正整數，對于每一個正整數 x 都有 1 <= x <= 1e5，
輸出
按從小到大的順序依次輸出這 n 個數字的公共質因數，每兩個數字之間用空格隔開，最后一個數字后面沒有空格，
如果它們沒有公共質因數則輸出 No，
最后換行，
樣例輸入
3
6 12 18
樣例輸出
2 3
HINT
來源
20-21(2)第0次線上賽
解：
1.篩法篩出1e5以下的素數，排序所給的數字以后回圈判斷每個素數是否是公因數（下面代碼），
2.（不需要篩法）(來自CST大佬)排序從小到大——拿a[0]找小于等于它的質數——得到質數判斷是不是公因數——是——輸出，
#include<iostream>
#include<cstring>
using namespace std;
const int N=100005;
int p[N];
int prime[N];
int cnt=0;
void xxs()
{
for (int i = 2; i <= N; i++)
{
if(p[i] == 0)
{
p[i]=i;
prime[cnt++]=i;
}
for (int j = 0;j<cnt;j++)
{
if (prime[j]>p[i]||prime[j]*i>N)
{
break;
}
p[prime[j]*i]=prime[j];
}
}
}
int main()
{
bool sc=0;
int sz[100005];
memset(sz,0,sizeof(sz));
xxs();
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>sz[i];
}
for(int i=0;i<cnt;i++)
{
for(int j=1;j<=n;j++)
{
if(sz[j]%prime[i]!=0) break;
else if(j==n)
{
if(sc==0)
{
cout<<prime[i];
sc=1;
}
else cout<<" "<<prime[i];
}
}
}
if(sc==0) cout<<"No";
cout<<endl;
return 0;
}
5:WSAD
描述
羅少在玩一個游戲，用 W S A D 分別控制角色進行 上 下 左 右 移動，我們可以把地圖看作一個二維平面，羅少初始站在原點，現在他操作了 n 次，請你輸出他的位置，
輸入
第一行是一個正整數 n 代表測驗案例的數量，(1 <= n <= 100)
每組案例是一個僅包含字符WSAD的字串 t 代表羅少的操作，(1 <= length(t) <= 100)
輸出
針對每組案例，輸出羅少操作以后所在位置的橫縱坐標，兩者之間用空格隔開，然后換行，
樣例輸入
2
WWW
SSD
樣例輸出
0 3
1 -2
HINT
來源
20-21(2)第0次線上賽
解：
1、回圈判斷字串每一個字符（下面代碼），
2、（來自CST大佬）使用count計算WASD的個數，直接計算，
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x=0,y=0;
string s;
cin>>s;
int lg=s.size();
for(int j=0;j<=lg;j++)
{
if(s[j]=='W') y++;
if(s[j]=='S') y--;
if(s[j]=='A') x--;
if(s[j]=='D') x++;
}
cout<<x<<" "<<y<<endl;
}
return 0;
}
6:陣列的貢獻值
描述 羅少經常刷題，這天他又看到了一道很有意思的題目，給定一個長度為 n 的陣列，定義陣列的貢獻值為陣列中 每個數首次出現的位置 * 每個數出現的次數 之和（相同的數字只計算一次），
例如：1 2 2 3 1，數字 1 首次出現的位置是 1，總共出現了 2 次，所以提供 1 * 2 = 2 的貢獻值，數字 2 是 2 * 2 = 4，數字 3 是 4 * 1 = 4，因此這個陣列的貢獻值為 2 + 4 + 4 = 10，
但很顯然這樣是難不倒羅少的，所以附加了一個條件，你可以任意改變陣列中數的位置，問改變后陣列最大的貢獻值是多少？
輸入
第一行是一個正整數 T 代表測驗案例的數量，(1 <= T <= 10)
每組案例包含一個正整數 n ，代表陣列的長度，(1 <= n <= 100000)
然后是 n 個整數 ai，(|ai| <= 10000)
輸出
針對每組案例，輸出改變數字位置后可以得到的最大陣列貢獻值，然后換行，
樣例輸入
2
4
1 2 1 2
4
1 1 2 2
樣例輸出
8
8
HINT
注意：陣列也可以不發生改變，
對于樣例1：1 2 1 2
改變前陣列的貢獻值為 1 * 2 + 2 * 2 = 6
你可以把他改為 1 1 2 2 或者 2 2 1 1 得到更大的陣列的貢獻值 8，
來源
20-21(2)第0次線上賽
解：
無（太難了QWQ）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266982.html
標籤：其他
上一篇：演算法模板：并合集
下一篇：[藍橋杯]地宮取寶