原文鏈接,球球不要爬我了
打著打著，學校停電了，gank了一波，應該是能寫的更快的，
A 題目鏈接
題意
給你一個陣列，按順序輸出最左、最右、次左、次右、次次左、次次右…
解題思路
水題，定義一左一右的兩個指標去模擬就好了，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=305;
LL t,n;
LL a[maxn],l,r;
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
t=read();
while(t--){
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
l=1,r=n;
for(int i=1;i<=n;++i){
if(i&1)
printf("%lld ",a[l++]);
else
printf("%lld ",a[r--]);
}
printf("\n");
}
return 0;
}
B 題目鏈接
題意
給你一個數字串，你可以洗掉連續的一段，也可以不洗掉，問能否構成‘2020’，
解題思路
水題，最后要構成‘2020’，就要洗掉len-4長度的連續的串，列舉洗掉的位置，去判斷剩余的4個數字是否能構成’2020’即可，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=205;
char s[maxn];
LL t,n;
bool init(){
LL len=strlen(s+1);
if(len<4)
return false;
if(s[1]=='2'&&s[2]=='0'&&s[3]=='2'&&s[4]=='0')
return true;
if(s[1]=='2'&&s[2]=='0'&&s[3]=='2'&&s[len]=='0')
return true;
if(s[1]=='2'&&s[2]=='0'&&s[len-1]=='2'&&s[len]=='0')
return true;
if(s[1]=='2'&&s[len-2]=='0'&&s[len-1]=='2'&&s[len]=='0')
return true;
if(s[len-3]=='2'&&s[len-2]=='0'&&s[len-1]=='2'&&s[len]=='0')
return true;
return false;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
t=read();
while(t--){
n=read();
scanf("%s",s+1);
if(init())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
C 題目鏈接
題意
水題，給你一個正數x，找到一個最小的正整數，它的位數和等于x，并且所有數字都是不同的，
解題思路
很明顯由1~9的數字最多構成45，要求最小，則可以將最大的數放在個位，次大的放在十位，以此類推，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
LL t,n;
LL get_ans(LL a){
if(a>45)
return -1;
LL ans=0,cas=0;
for(int i=9;i>=1;--i){
if(a>=i){
ans+=i*pow(10,cas++);
a-=i;
}
}
return ans;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
t=read();
while(t--){
n=read();
LL ans=get_ans(n);
printf("%lld\n",ans);
}
return 0;
}
D 題目鏈接
題意
有一個陣列，每次可以合并相鄰的兩個位置，求讓陣列內的所有的元素都是相等時，最小合并次數，
解題思路
要求所有元素都相等，sum為所有a[i]之和，則此時元素的值一定是sum的因子，然后去列舉因子p，將陣列分為sum/p份，對于每一份來說，它們肯定是連續的一整段，去判斷是否可以滿足要求即可，因為最后是有sum/p份，所以合并次數為n-sum/p，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=3005;
LL t,n,a[maxn],sum;
bool init(LL p){
LL q=0;
for(int i=1;i<=n;++i){
q+=a[i];
if(q>p)
return false;
if(q==p)
q=0;
}
return true;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
t=read();
while(t--){
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
sum=0;
for(int i=1;i<=n;++i)
sum+=a[i];
for(int p=1;p<=sum;++p)
if(sum%p==0&&init(p)){
printf("%lld\n",n-sum/p);
break;
}
}
return 0;
}
E1 題目鏈接
題意
有n個數字，讓你求有多少個三元組滿足max(a[i],a[j],a[k])-min(a[i],a[j],a[k])<=2 (i<j<k)，
解題思路
每次列舉a[i]，得到a[i]，a[i]+1，a[i]+2的個數，每次從這三類數里頭選出三個數字，肯定滿足要求，a[i]那組一定要選這樣列舉下一個a[i]時就不會有重復的情況，方案數為：在a[i]中選擇3個、在a[i]中選擇2個且在a[i]+1中選擇1個、在a[i]中選擇2個且在a[i]+2中選擇1個、在a[i]中選擇1個且在a[i]+1中選擇2個、在a[i]中選擇1個且在a[i]+2中選擇2個、在a[i]中選擇1個且在a[i]+1中選擇1個且在a[i]+2中選擇1個，用排列組合去寫，注意一點，由于T挺大的，直接memset會超時，
沒注意貢獻一發罰時，先用map存一下用過哪些再去初始化，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=2e5+5;
LL t,n,m,k,conn[maxn+5],a;
LL C(LL n, LL r) //回傳C(n,r)
{
if(n<r)
return 0;
LL sum = 1;
for (LL i = 1; i <= r; i++)
sum = sum*(n + 1 - i) / i;
return sum;
}
map<int,int> use;
LL get_ans(LL pos){
LL a=conn[pos],b=conn[pos+1],c=conn[pos+2];
return C(a,3)+C(a,2)*C(b,1)+C(a,2)*C(c,1)+C(a,1)*C(b,2)+C(a,1)*C(c,2)+a*b*c;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
t=read();
while(t--){
for(auto it=use.begin();it!=use.end();++it){
int fi=it->first;
conn[fi]=0;
}
use.clear();
// memset(conn,0,sizeof conn);
n=read();
m=3;
k=2;
for(int i=1;i<=n;++i){
a=read();
++conn[a];
use[a]=1;
}
LL ans=0;
for(auto it=use.begin();it!=use.end();++it){
int fi=it->first;
ans+=get_ans(fi);
}
printf("%lld\n",ans);
}
return 0;
}
E2也是能寫出來的，比賽時沒想到，差一點，明天再來跟新，
跟新時間 2020-12-17 16:17
原本是打算昨天下午跟新的，室友找我打游戲就咕咕咕了 ，
回到正題，比賽期間只看了下E2，沒去看F題，其實F題也是很簡單的，如果不停電應該能寫出來，
E2 題目鏈接
題意
有n個數字，讓你求有多少個m元組滿足max(a[i_1],a[i_2],…a[i_m])-min(a[i_1],a[i_2],…a[i_m])<=k (i_1<i_2…<i_m)，
解題思路
E1的升級版，也是一樣的做法，每次列舉a[i]，得到a[i]的個數和a[i+1，i+k]個數的和sum，（當時寫E1時死腦筋的把后面的情況全部列舉出來，其實沒必要，只要在sum中選擇就好了，不用再細分），每次只要再a[i]中選擇p個，再從sum中選擇m-p個（p>0），這樣列舉下一個a[i]時就不會有重復的情況，之后就用組合數求就好了，由于要取模，所以先階乘打表預處理一下，
由于T挺大的，直接memset會超時，先用map存一下用過哪些再去初始化，
還有就是求sum的程序，如果每次從for回圈的去加[i+1，i+k]的和，O(n*k)會超時，考慮使用上次求出的sum遞推去求這次的sum，
這里定義一下SUM(a[i，j])表示：a[i]的個數+a[i+1]的個數+…+a[j]的個數，
設fi為這次列舉的a[i]的值，last為上次列舉的fi，last_sum為上個狀態的和，即last_sum=SUM(a[last+1，last+k])，以上三個值都是已知的，求此時的sum，即a[fi+1，fi+k]個數的和，如果fi>=last+k，則sum只能O(k)去計算，如果fi<last+k，則可以利用last_sum，先讓sum=last_sum，再減去SUM(a[last+1，fi])，最后再加上SUM(a[last+k+1，fi+k])，即sum=last_sum-SUM(a[last+1，fi])+SUM(a[last+k+1，fi+k])，仔細思考一下，因為是map去列舉的a[i]，所以last到fi之前是沒有數的，所以SUM(last+1，fi-1)=0，所以最后sum=last_sum-a[i]的個數+SUM(a[last+k+1，fi+k])，時間復雜度為O(n)，
代碼中并沒有用到last_sum，這么說只是方便理解，最好再草稿紙上畫畫，注意下for回圈的上界，這里就不說了，細節見代碼吧，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=2e5+5;
const int mod=1e9+7;
LL t,n,m,k,a,conn[maxn],sum[maxn];
LL fact[maxn],infact[maxn]; // 階乘 逆元
LL inv[maxn];
void init(){ // 預處理階乘與階乘逆元
fact[0]=infact[0]=inv[1]=1;
for(int i=2;i<maxn;++i)
inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<maxn;++i){
fact[i]=fact[i-1]*i%mod;
infact[i]=infact[i-1]*inv[i]%mod; // 線篩求逆元 若mod不為質數 則用擴歐求逆元
}
}
LL C(LL n,LL r){
if(n<r)
return 0;
return fact[n]%mod*infact[r]%mod*infact[n-r]%mod;
}
map<int,bool> use;
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
init();
t=read();
while(t--){
n=read();
m=read();
k=read();
for(auto it=use.begin();it!=use.end();++it)
conn[it->first]=0;
use.clear();
//memset(conn,0,sizeof conn);
for(int i=1;i<=n;++i){
a=read();
++conn[a];
use[a]=true;
}
LL ans=0,last=0,sum=0,up;
for(int i=last+1;i<=last+k;++i)
sum+=conn[i];
for(auto it=use.begin();it!=use.end();++it){
LL fi=it->first;
up=min(fi+k,n);
if(fi>=last+k){
sum=0;
for(int i=fi+1;i<=up;++i)
sum+=conn[i];
}else{
sum-=conn[fi];
for(int i=last+k+1;i<=up;++i)
sum+=conn[i];
}
last=fi;
up=min(conn[fi],m);
for(int i=1;i<=up;++i){
ans+=C(conn[fi],i)*C(sum,m-i)%mod;
ans%=mod;
}
}
printf("%lld\n",ans);
}
return 0;
}
F 題目鏈接
題意
有n個區間，問你最少洗掉多少個區間，使得存在一個區間與其它的區間都有交集，
解題思路
這題我覺得比E2簡單，但是比賽時做對的人比E2少好多，
將區間的L和R分別拆開然后從小到大排序，得到排序后的L陣列與R陣列，
列舉每個區間，得到l與r，再R陣列中二分查找第一個大于等于l的位置pos，pos-1就是在此區間左側且不相交的區間個數，再L陣列中二分查找第一個大于r的位置pos，n-pos+1就是在此區間右側且不相交的區間個數，相加求個最小值即可，
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
char c=getchar();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=2e5+5;
struct node{
LL l,r;
};
node a[maxn];
LL t,n,a_l[maxn],a_r[maxn];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
t=read();
while(t--){
n=read();
for(int i=1;i<=n;++i){
a[i].l=read();
a[i].r=read();
a_l[i]=a[i].l;
a_r[i]=a[i].r;
}
sort(a_l+1,a_l+1+n);
sort(a_r+1,a_r+1+n);
LL ans=n;
for(int i=1;i<=n;++i){
LL l=a[i].l,r=a[i].r;
LL pos_l=lower_bound(a_r+1,a_r+1+n,l)-a_r-1;
LL pos_r=upper_bound(a_l+1,a_l+1+n,r)-a_l;
ans=min(ans,pos_l+n-pos_r+1);
}
printf("%lld\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/236151.html
標籤：其他
上一篇：作業系統期末復習——概念和簡答題