文章目錄
- A：會寫腳本的月月鳥
- B：別看了 這是水題
- C：ACM脫單大法
- D：Love_Jacques學長的游戲思維
- E：后綴自動機next指標dag圖上跑SG函式
- F：新建 Microsoft PowerPoint 演示文稿.pptx
- G：禁止復讀
- H：嚇得我趕緊出了個簽到題
A：會寫腳本的月月鳥
解法1：
首先讀了一下題目，嗷，水題，很快啊很快，有的同學啪的一下就來了一個暴力，然后就TLE了，
仔細分析一下這個序列長度
2
?
1
0
5
2*10^5
2?105,在看詢問的次數
1
?
1
0
5
1*10^5
1?105,如果每次詢問都是1-n，這樣時間復雜度是不是
O
(
n
?
m
)
=
2
?
1
0
10
O(n*m)=2*10^{10}
O(n?m)=2?1010 ,看起來不可行，
所以我們想個辦法來優化一下演算法，每次詢問區間
[
l
?
r
]
[l-r]
[l?r]所有值得 與 運算，
這個與在二進制中有什么特性嗎？
兩個位都為1時，結果才為1
例如：10001&10100=10000
我們這樣思考，如果把每個數看成由二進制組成得，每個數都小于1e9，也就是說對應得二進制位數最多只有31位，嗷，也就是說這個這個數就可以當成這個二進制每位對應十進制的大小之和，
比如說：110101對應的十進制大小就是
1
?
2
0
+
0
?
2
1
+
1
?
2
2
+
0
?
2
3
+
1
?
2
4
+
1
?
2
5
1*2^0+0*2^1+1*2^2+0*2^3+1*2^4+1*2^5
1?20+0?21+1?22+0?23+1?24+1?25
我們可以把這整個區間的每個數拆分成31份，對每位分別進行&運算后，最后把這31份的結果相加即可，那么問題就轉換成如何快速的求出每一份的值是多少？
通過與運算我們可以知，假設這段區間每個數二進制的最低位 進行&運算，如果這段區間任意一個數二進制的最低位是0，那么算出來的最低位&的值即為0.
當我們分成31份進行計算時，對于二進制的某一位，序列是否出現過0，如果出現過0，則計算后這一位的結果是0，
到這里，題目就變成，對于某個區間，查詢0的個數了，只不過要查找31次（因為有31位），
O（1）時間復雜度查詢的話，我們可以使用前綴和進行計算，
復雜度分析：
時間復雜度:
O
(
31
?
(
n
+
m
)
)
O(31*(n+m))
O(31?(n+m))
空間復雜度:
O
(
31
?
n
)
O(31*n)
O(31?n)
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
const int maxn =2e5+10;
typedef long long ll;
int dp[maxn][35];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
for(int j=0;j<31;j++){
if(((x>>j)&1)==0) dp[i][j]=dp[i-1][j]+1;
else dp[i][j]=dp[i-1][j]; //前綴預處理0的個數
}
}
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
int ans=0;
for(int j=0;j<31;j++){
if(dp[y][j]-dp[x-1][j]==0) //如果等于0，代表這段區間這一位沒有0出現
ans+=(1<<j);
}
printf("%d\n",ans);
}
return 0;
}
解法2：
線段樹，樹狀陣列暴力莽一波，（建議先學會簡單解法）
不過多介紹了，有興趣的同學可以了解一下，
在建樹后，它可以讓單次查詢的復雜度降為
O
(
l
o
g
n
)
O(logn)
O(logn)
復雜度分析：
時間復雜度:
O
(
n
+
m
?
l
o
g
n
)
)
O(n+m*logn))
O(n+m?logn))
空間復雜度:
O
(
4
?
n
)
O(4*n)
O(4?n)
線段樹代碼：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
const int maxn =2e5+10;
typedef long long ll;
int tree[maxn<<2];
int a[maxn];
int n,m;
void build(int node,int l,int r){
if(l==r){
tree[node]=a[l];
return ;
}
int mid=(l+r)/2;
if(l<=mid) build(node*2,l,mid);
if(r>mid) build(node*2+1,mid+1,r);
tree[node]=tree[node*2]&tree[node*2+1];
}
int query(int node,int start,int ends,int l,int r){
if(start>=l&&ends<=r){
return tree[node];
}
int mid=(start+ends)/2;
int ans=-1;
if(l<=mid) ans=ans&query(node*2,start,mid,l,r);
if(r>mid) ans=ans&query(node*2+1,mid+1,ends,l,r);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
for(int i=0;i<m;i++){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(1,1,n,l,r));
}
return 0;
}
B：別看了 這是水題
題解：
這個題目算是一個構造題，按照題目要求構造出一個序列，
解法肯定會有很多種，當然不同解法輸出的序列也不一樣，這里介紹一種解法，
首先判斷它是否能構成這樣的序列，
如果
k
?
2
<
=
n
k*2<=n
k?2<=n，那么可以構成，反之輸出-1.（別問我為什么）
那么我們接下來就需要找一個通用的順序來輸出一下這個序列了，
解法1： 將序列攔腰斬斷，分成兩半，左邊輸出一個值，右邊輸出一個值（重復操作），以保證間隔大于等于k，
復雜度分析：
時間復雜度:
O
(
n
)
O(n)
O(n)
空間復雜度:
O
(
n
)
O(n)
O(n)
解法1代碼：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
const int maxn =2e5+10;
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d%d",&n,&k);
if(n==1){ //特判長度1的序列
printf("1\n");
}
else if(k*2<=n){
int temp=n/2;
if(n%2==1){ //長度為奇數時
for(int i=2;i<=temp+1;i++){
printf("%d %d ",i+temp,i);
}
printf("1\n");
}
else{ //長度為偶數時
for(int i=1;i<=temp;i++){
printf("%d %d ",i+temp,i);
}
printf("\n");
}
}
else printf("-1\n");
}
return 0;
}
代碼2：
許金龍大神’s code:
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while(T --) {
int n, k; cin >> n >> k;
if (n == 1) cout << "1\n";
else if (n < 2*k) cout << "-1\n";
else {
for(int i = k; i >= 1; -- i) {
for(int j = i; j <= n; j += k) {
cout << j << " ";
}
}
cout << "\n";
}
}
return 0;
}
C：ACM脫單大法
題解：
這個題目的解法也有很多，因為復雜度卡的不是很嚴格，時間復雜度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)應該都可以
比如說二分+暴力，后綴處理等，，
解法：
簡單的小貪心做一下（算半個貪心，
首先，如果有解，那么前半部分和后半部分的最大最小值肯定跟整個序列最大最小值是相同的，
這樣我們先遍歷一遍序列找出最大值和最小值，前半段區間最大最小值和后半段區間最大最小值肯定跟整個序列的相同，
我們遍歷一邊序列記錄下來第一個出現imax的位置maxpos和imin的位置minpos，
設
x
=
m
a
x
(
m
a
x
p
o
s
，
m
i
n
p
o
s
)
x=max(maxpos，minpos)
x=max(maxpos，minpos)然后從序列x+1這個位置遍歷序列，如果存在值等于最大值和存在值等于最小值，那么x就是答案，反之則輸出-1，
復雜度分析：
時間復雜度:
O
(
n
)
O(n)
O(n)
空間復雜度:
O
(
n
)
O(n)
O(n)
代碼：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
const int maxn =1e5+10;
typedef long long ll;
int a[maxn];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int imax=-2e9-10,imin=2e9+10;
int maxpos,minpos;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(imax<a[i]) imax=a[i],maxpos=i;
if(imin>a[i]) imin=a[i],minpos=i;
}
int st=max(maxpos,minpos);
bool xx=false,yy=false;
for(int i=st+1;i<=n;i++){
if(imax==a[i]) xx=true;
if(imin==a[i]) yy=true;
}
if(xx&&yy) printf("%d\n",st);
else printf("-1\n");
}
}
D：Love_Jacques學長的游戲思維
坑點1：
實數都有小數點嗎？
坑點2： 1.23與1.2300000
題解： 因為實數小于10，所以從左邊往右邊比較即可，注意一下不同長度字串的處理，可以把較短的字串后面全補為0，
復雜度分析：
時間復雜度:
O
(
n
)
O(n)
O(n)
空間復雜度:
O
(
n
)
O(n)
O(n)
代碼：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
const int maxn =1e5+10;
typedef long long ll;
char s[1100],s1[1100];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
scanf("%d",&t); //x的值 分別代表誰大誰小
while(t--){
scanf("%s",s);
scanf("%s",s1);
int lens=strlen(s);
int lens1=strlen(s1);
if(lens==1) s[1]='.',s[2]='\0',lens++; //判斷給出的是個整數還是實數，如果是實數則補全
if(lens1==1) s1[1]='.',s1[2]='\0',lens1++;
if(lens<lens1) for(int i=lens;i<lens1;i++) s[i]='0'; //補0
else for(int i=lens1;i<lens;i++) s1[i]='0';
int x=0;
for(int i=0;i<max(lens1,lens);i++){
if(s[i]>s1[i]){ //判斷大小，別忘記break
x=1;
break;
}
else if(s[i]<s1[i]){
x=2;
break;
}
}
if(x==0) printf("EASY GAME!\n");
else if(x==1) printf("AZNB\n");
else printf("YZNB\n");
}
}
E：后綴自動機next指標dag圖上跑SG函式
題解：
貪心
考慮并且購買第i個寶石的價格是
i
?
a
[
i
]
，
i*a[i]，
i?a[i]，
那么我們不斷拿第一個寶石即可，
但是寶石的價格可能是負數，所以遇到價格位負數的寶石（倒貼你錢），我們如何最大化他的值呢，題目可知，想讓他倒貼給你錢最多，也就是這個寶石初始位置下標乘a[i]即可，
也可以理解為，先從后往前把小于零的寶石買掉，然后在第一個位置一直買即可，
復雜度分析：
時間復雜度:
O
(
n
)
O(n)
O(n)
空間復雜度:
O
(
1
)
O(1)
O(1)
代碼：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
const int maxn =1e5+10;
typedef long long ll;
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
scanf("%d",&n);
ll ans=0;
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
if(x<0) ans+=x*i;
else ans+=x;
}
printf("%lld",ans);
return 0;
}
F：新建 Microsoft PowerPoint 演示文稿.pptx
題解：
暴力即可，設一個陣列記錄所有出現過的數有哪些，每次從1開始找最小沒有出現過的數是什么，
復雜度分析：
時間復雜度:
O
(
n
2
)
O(n^2)
O(n2)
空間復雜度:
O
(
n
)
O(n)
O(n)
代碼：
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
typedef long long ll;
const int mod = 1e9+7;
int a[1000+10];
int se(){ //查找未出現過的最小下標
for(int i=1;i<=1000;i++){
if(!a[i]) return i;
}
return -1;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<1000;i++) a[i]=0; //可寫可不寫（全域變數初始值為0，可以不寫
while(n--){
int opt,x;
scanf("%d",&opt);
if(opt==1){
int pos=se();
a[pos]=1; //標記該結點出現過，為后面洗掉提供遍歷
if(pos==1) printf("新建 Microsoft PowerPoint 演示文稿.pptx\n");
else printf("新建 Microsoft PowerPoint 演示文稿(%d).pptx\n",pos);
}
else{
scanf("%d",&x);
if(a[x]){ //查詢該結點是否出現過，
printf("Successful\n");
a[x]=0;
}
else printf("Failed\n");
}
}
return 0;
}
ps：這個題也有更優的解法，用優先佇列即可，學有余力的同學可以嘗試一下，思想就是是，一開始把所有未出現的檔案全都塞到優先佇列中（小頂錐），每次取優先佇列頭，然后洗掉優先佇列頭節點，如果遇到洗掉改結點，如果這個結點存在，再把這個結點塞進優先佇列即可，
復雜度分析：
時間復雜度:
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
空間復雜度:
O
(
n
)
O(n)
O(n)
代碼：
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<bits/stdc++.h>
const int maxn =2e5+10;
typedef long long ll;
using namespace std;
int visited[maxn];
signed main(){
// freopen("27.in","r",stdin);
// freopen("27.out","w",stdout);
int n;
cin>>n;
memset(visited,false,sizeof visited);
priority_queue<int,vector<int>,greater<int>> q;
for(int i=1;i<=n;i++){ //未出現的全部塞進優先佇列
q.push(i);
}
for(int i=0;i<n;i++){
int opt,x;
scanf("%d",&opt);
if(opt==1){
int t=q.top(); //每次取最小元素
q.pop();
visited[t]=true;
if(t==1) printf("新建 Microsoft PowerPoint 演示文稿.pptx\n");
else{
printf("新建 Microsoft PowerPoint 演示文稿(%d).pptx\n",t);
}
}
else{
scanf("%d",&x);
if(visited[x]){
printf("Successful\n");
visited[x]=false;
q.push(x); //洗掉了改元素，把元素重新放回優先佇列，
}
else printf("Failed\n");
}
}
return 0;
}
G：禁止復讀
題解：
用一下c++的sort是我最后寫c語言報告的倔強了，不會的同學學一下嘛，真的很好用QAQ，
這個只要搞清楚如何判斷一個人是否發起復讀是最重要的事情，
假設你要判斷第i個人是否為復讀發起者
那么你就要檢查一下第i-1個人說的話是不是跟他一樣
并且第i-2個熱播說的話跟他不一樣
如果這兩者都符合，那么這個人就是復讀發起者，
還有一點就是去重，可能一個人會復讀好幾次，但是你只需要輸出一次他的序列即可，
你可以設定一個陣列記錄已經被記錄下來的人，也可以最后對序列進行去重即可，
復雜度分析：
時間復雜度:
O
(
∣
s
∣
?
n
)
O(|s|*n)
O(∣s∣?n)
空間復雜度:
O
(
∣
s
∣
?
n
)
O(|s|*n)
O(∣s∣?n)
代碼：
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
char s[1010][55];
int visited[1010];
int ans[1010];
int judge(char a[],char b[]){
int lena=strlen(a);
int lenb=strlen(b);
if(lena!=lenb) return 0;
for(int i=0;i<lena;i++) if(a[i]!=b[i]) return 0;
return 1;
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
int n,cnt=0;
scanf("%d",&n);
for(int i=2;i<=n+1;i++){
int opt;
scanf("%d",&opt);
scanf("%s",s[i]);
if(judge(s[i],s[i-1])&&!judge(s[i],s[i-2])){
if(!visited[opt]){
visited[opt]=1;
ans[cnt++]=opt;
}
}
}
std::sort(ans,ans+cnt);
printf("%d\n",cnt);
for(int i=0;i<cnt;i++) printf("%d ",ans[i]);
printf("\n");
}
H：嚇得我趕緊出了個簽到題
那串代碼得意思：
其實是個splay，平衡樹的一種，花里胡哨的一頓亂操作其實沒啥用處，
為什么會輸出lcltql！是因為對這個數每次添加一個結點（正整數），然后對樹進行求和操作，一共求和了七次（當然也添加了七次，每添加一次求和一次），讓著七次的值正好等于每個字母對應的ASCII碼即可，
/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fin(filename) freopen(filename,"r",stdin)
#define fout(filename) freopen(filename,"w",stdout)
#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =2e5+10;
const int MaxN = 1e9+7;
const int MinN = -1e9+7;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e8;
const int N = 5e6 + 100;
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cout<<"ACDA"<<endl;
cout<<"lcltql!"<<endl;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239131.html
標籤：其他
上一篇：異數OS 開放式閉源繼承人協議