CPE二星筆記:pencil:

---

目錄

001~100		101~200		201~300
151		10233		11043
245		10236		11051
255		10238		11056
294		10252		11057
337		10256		11067
374		10263		11076
378		10264		11078
397		10266		11086
406		10267		11093
495		10283		11094
514		10284		11096
516		10286		11115
534		10287		11121
536		10289		11157
540		10293		11235
572		10295		11241
612		10297		11264
657		10298		11286
674		10299		11287
679		10301		11308
686		10302		11326
696		10305		11335
722		10311		11340
748		10312		11344
821		10315		11348
900		10322		11350
924		10325		11360
967		10327		11369
991		10333		11396
993		10334		11403
997 Show the Sequence	link	10336		11412
1200		10338		11417	link
1210		10339		11418
1262		10341		11462
1644		10343		11475
1730		10344		11480
1753		10345		11484
10001		10347		11505
10002		10348		11507
10004 Bicoloring	link	10352		11508
10006		10360		11515
10009		10368		11518
10010		10371		11519
10013 Super long sums	link	10372		11520
10014		10382		11536
10015		10405		11538
10016		10406		11550
10017		10407		11583
10020		10408		11586
10028		10427		11609
10034		10432		11614
10039		10440		11615
10040		10450		11616
10060		10466		11629
10061		10489		11683
10063		10494		11692
10064		10497		11703
10066		10504		11714
10070		10508		11729
10077		10523		11730
10098		10527		11742
10100		10535		11847
10102		10555		11849
10104		10563		11850
10106		10579		11879
10107		10583		11898
10110		10596		11953
10114		10608		11957
10115		10611		11991
10116		10625		11995
10125		10666		11997
10127		10670		12160
10137		10673		12207
10138		10684		12382
10140		10700		12406 Help Dexter	link
10141		10718		12455 Bars	link
10145		10738		12592 Slogan Learning of Princess	link
10142		10730		12545 Bits Equalizer	link
10146		10763		12694 Meeting Room Arrangement	link
10152		10815		12705 Breaking Board	link
10160		10820		12797 Letters	詳解
10161		10858		12844
10167		10871		13185 DPA Numbers I	詳解
10172		10881		13194 DPA Numbers II	詳解
10174		10887
10176		10901
10180		10902
10182		10910
10192		10915
10193		10916
10194		10920
10195		10924
10196		10926
10197		10930
10200		10936
10205		10940
10220		10959
10223		11013
10225		11039
10227		11040

---

151

245

255

294

337

374

378

397

406

495

514

516

534

536

540

572

612

657

674

679

686

696

722

748

821

900

924

967

991

993

997_Show_the_Sequence

題目簡述:book:

體感難度：★★
Browse Problem

詳解:pencil2:(知識點：找規律)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
	string str;
	int N,x;
	char ch;
	while(cin>>str>>N){
		stack<char> stk;
		vector<char> op;
		vector<int> v0,v1;
		stringstream ss(str);
		while(ss>>ch){
			if(ch=='*'||ch=='+')
				op.push_back(ch);
			else if(isdigit(ch)||ch=='-'){
				ss.unget();
				ss>>x;
				v0.push_back(x);
			}
		}
		reverse(v0.begin(),v0.end());
		reverse(op.begin(),op.end());
		v1=vector<int>(v0.size(),0);
		for(int j=1;j<v0.size();j++){
			if(op[j-1]=='*')
				v0[j]=v0[j-1]*v0[j];
		}
		cout<<*v0.rbegin();
		for(int i=1;i<N;i++){
			v1[0]=v0[0];
			for(int j=1;j<v1.size();j++){
				if(op[j-1]=='+')
					v1[j]=v0[j-1]+v0[j];
				else
					v1[j]=v1[j-1]*v0[j];
			}
			cout<<' '<<*v1.rbegin();
			v0.swap(v1);
		}
		cout<<'\n';
	}
}

1200

1210

1262

1644

1730

1753

10001

10002

10004_Bicoloring

Browse Problem

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,m,a,b;
	while(cin>>n,n){
		cin>>m;
		vector<int> g[210],vis(210);
		while(m--){
			cin>>a>>b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		try{
			for(int i=0;i<n;i++){
				stack<int> s;
				if(vis[i]==0)
					vis[i]=1,s.push(i);
				while(s.size()){
					int node=s.top();
					s.pop();
					for(int child:g[node]){
						if(vis[child]==0){
							s.push(child);
							vis[child]=(vis[node]==1 ? 2:1);
						} 
						else if(vis[child]==vis[node]){
							throw 1;
						}
					}
				}
			}
			cout<<"BICOLORABLE.\n";
		}
		catch(int e){
			cout<<"NOT BICOLORABLE.\n";
		}
		
	}
}

10006

10009

10010

10013_Super_long_sums

體感難度：★
Browse Problem

詳解:pencil2:(知識點：大數加法)

參考程式碼

Browse Problem

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	char ch;
	cin>>t;
	while(t--){
		string s1,s2,c,ans;
		int a,b,n;
		cin>>n;
		while(n--){
			cin>>a>>b;
			s1.push_back(a);
			s2.push_back(b);
		}
		reverse(s1.begin(),s1.end());
		reverse(s2.begin(),s2.end());
		ans=c=string(s1.size()+1,0);
		for(int i=0;i<s1.size();i++){
			c[i+1]=(s1[i]+s2[i]+c[i])/10;
			ans[i]=(s1[i]+s2[i]+c[i])%10;
		}
		if(*c.rbegin()==char(1))
			*ans.rbegin()=1;
		else
			ans.pop_back();
		for(int i=ans.size()-1;i>=0;i--)
			cout<<int(ans[i]);
		cout<<'\n';
		if(t!=0)
			cout<<'\n';
	}
}

python速解

t=int(input())
for tt in range(t):
	ch=input()
	n=int(input())
	ans=0
	for i in range(n):
		a,b=map(int,input().split())
		ans+=(a+b)*10**(n-1-i)
	print(ans,end="\n\n")

10014

10015

10016

10017

10020

10028

10034

10039

10040

10060

10061

10063

10064

10066

10070

10077

10098

10100

10102

10104

10106

10107

10110

10114

10115

10116

10125

10127

10137

10138

10140

10141

10142

10145

10146

10152

10160

10161

10167

10172

10174

10176

10180

10182

10192

10193

10194

10195

10196

10197

10200

10205

10220

10223

10225

10227

10233

10236

10238

10252

10256

10263

10264

10266

10267

10283

10284

10286

10287

10289

10293

10295

10297

10298

10299

10301

10302

10305

10311

10312

10315

10322

10325

10327

10333

10334

10336

10338

10339

10341

10343

10344

10345

10347

10348

10352

10360

10368

10371

10372

10382

10405

10406

10407

10408

10427

10432

10440

10450

10466

10489

10494

10497

10504

10508

10523

10527

10535

10555

10563

10579

10583

10596

10608

10611

10625

10666

10670

10673

10684

10700

10718

10730

10738

10763

10815

10820

10858

10871

10881

10887

10901

10902

10910

10915

10916

10920

10924

10926

10930

10936

10940

10959

11013

11039

11040

11043

11051

11056

11057

11067

11076

11078

11086

11093

11094

11096

11115

11121

11157

11235

11241

11264

11286

11287

11308

11326

11335

11340

11344

11348

11350

11360

11369

11396

11403

11412

11417_GCD

體感難度：★
Browse Problem

詳解:pencil2:(知識點：大數加法)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	while(cin>>n,n){
		long long int ans=0;
		for(int i=1;i<n;i++)
			for(int j=i+1;j<=n;j++)
				ans+=__gcd(i,j);
		cout<<ans<<'\n';
	}
}

11418

11462

11475

11480

11484

11505

11507

11508

11515

11518

11519

11520

11536

11538

11550

11583

11586

11609

11614

11615

11616

11629

11683

11692

11703

11714

11729

11730

11742

11847

11849

11850

11879

11898

11953

11957

11991

11995

11997

12160

12207

12382

12406_Help_Dexter

Mon, Jul 18, 2022 10:16 PM

題目簡述:book:

體感難度：★★
Browse Problem

詳解:pencil2:(知識點：利用二進位窮舉)

參考程式碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int t,p,q;
    int pow2[18]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
    cin>>t;
    for(int d=1;d<=t;d++){
        cin>>p>>q;
        set<int> s;
        for(int i=0;i<pow2[p];i+=2){
            int num=0,k=i,digits=1;
            for(int r=1;digits<=p;r*=10,digits++){
                num+=(k&1?1:2)*r;
                k>>=1;
            }
            if(num%pow2[q]==0)s.insert(num);
        }
        cout<<"Case "<<d<<": ";
        if(s.size()==0)cout<<"impossible"<<endl;
        else if(s.size()==1)cout<<*s.begin()<<endl;
        else cout<<*s.begin()<<' '<<*s.rbegin()<<endl;
    }
}

---

12455_Bars

Mon, Jul 18, 2022 8:21 PM

題目簡述:book:

體感難度：★
Browse Problem

詳解:pencil2:(知識點：利用二進位窮舉)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n,p;
    cin>>t;
    while(t--){
        bool OK=0;
        cin>>n>>p;
        vector<int> v(p);
        for(int i=0;i<p;i++)cin>>v[i];
        for(int i=0;i<pow(2,p)&&!OK;i++){
            int k=i,len=0;
            for(int cur=0;k;cur++){
                if(k%2)len+=v[cur];
                k>>=1;
            }
            OK=(len==n);
        }
        cout<<(OK?"YES":"NO")<<endl;
    }
}

---

12592_Slogan_Learning_of_Princess

Tue, Jul 19, 2022 7:14 PM

題目簡述:book:

體感難度：0
Browse Problem

:pencil:(知識點 : map)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string a,b;
    map<string,string> m;
    cin>>n>>ws;
    while(n--){
        getline(cin,a);
        getline(cin,b);
        m[a]=b;
    }
    cin>>n>>ws;
    while(n--){
        getline(cin,a);
        cout<<m[a]<<endl;
    }
}

---

12545_Bits_Equalizer

Mon, Jul 18, 2022 8:21 PM

題目簡述:book:

體感難度：★★
Browse Problem

詳解:pencil2:(知識點：貪心)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int k=1;k<=n;k++){
        string s,t;
        int step=0,d=0,add=0; //d=sumT-sumS
        cin>>s>>t;
        for(int i=0;i<s.size();i++)d+=(t[i]=='1')-(s[i]=='1');
        if(d<0){
            cout<<"Case "<<k<<": -1"<<endl;
            continue;
        }
        for(int i=0;i<s.size();i++){ //處理'?'
            if(s[i]!='?')continue;
            if(d>0 && t[i]=='1')s[i]='1',d--;
            else s[i]='0';
            step++;
        }
        for(int i=0;i<s.size()&&d>0;i++){ //補'1'
            if(s[i]=='0'&&t[i]=='1'){
                s[i]='1';
                d--,step++;
            }
        }
        for(int i=0;i<s.size();i++) // XOR
            add+=!(s[i]==t[i]);
        step+=(add/2);
        cout<<"Case "<<k<<": "<<step<<endl;
    }
}

---

12694_Meeting_Room_Arrangement

Mon, Jul 18, 2022 7:14 PM

題目簡述:book:

體感難度：★
Browse Problem

詳解:pencil2:(知識點：工作排程貪心)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,a,b;
    cin>>t;
    while(t--){
        vector<pair<int,int>> v; //pair<end,start>
        while(cin>>a>>b,a||b)v.push_back({b,a});
        sort(v.begin(),v.end());
        int back=v[0].first,ans=1;
        for(int i=1;i<v.size();i++){
            if(v[i].second>=back){
                back=v[i].first;
                ans++;
            }
        }
        cout<<ans<<endl;
    }
}

---

12705_Breaking_Board

Mon, Jul 18, 2022 6:45 PM

題目簡述:book:

體感難度：★
Browse Problem

詳解:pencil2:(知識點：map+權重排序)

參考程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t>>ws;
    while(t--){
        int sum=0;
        string s;
        getline(cin,s);
        int cost[36]={2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,9,9,9,9,10,10,10,11,11,12};
        map<char,int> num,index;
        priority_queue<pair<int,char>> pq;
        for(char &e:s)if(e!=' ')num[e]++;
        for(auto &it:num) pq.push({it.second,it.first});
        for(int i=0;pq.size();i++){
            index[pq.top().second]=i;
            pq.pop();
        }
        for(char &e:s)if(e!=' ')sum+=cost[index[e]];
        cout<<sum<<endl;
    }

}

---

12797_Letters

Mon, Jul 18, 2022 12:01 PM

題目簡述:book:

體感難度：★★★
Browse Problem

• 多筆測資EOF板。
• 在n*n的字元陣列中，找(0,0)->(n-1,n-1)之最短路徑，其中路徑上不可同時存在同字母之大小寫。

詳解:pencil2: (知識點：二進位+BFS)

步驟一 找字母大小寫分布

窮舉路徑上字母大小寫分布可能(0：只允許小寫 1：只允許大寫)

index	0	1	2	3	4	5	6	7	8	9
letter	A	B	C	D	E	F	G	H	J	I
i=0	0	0	0	0	0	0	0	0	0	0
i=1	1	0	0	0	0	0	0	0	0	0
i=2	0	1	0	0	0	0	0	0	0	0
i=3	1	1	0	0	0	0	0	0	0	0

//利用二進位性質可窮舉vector<bool> t(10)之所有排列
for(int i=0;i<1024;i++){
    vector<bool> t(10);
    for(int cur=0,k=i;k;k>>=1)t[cur++]=k&1;
} 

步驟二 找最短路徑

對每一種大小寫分布可能分別進行BFS找出最短路徑。

參考程式碼

#include<bits/stdc++.h>
#define oo 10010
using namespace std;
typedef tuple<int,int,int> tiii;
int dr[4]{-1,0,0,1},dc[4]{0,-1,1,0},ans;
int isup(char &ch){
    return (ch<97);
}
int toi(char &ch){
    return isup(ch)?ch-65:ch-97;
}
void bfs(vector<string> v,vector<bool> &t,int n){
    queue<tiii> q;
    int flag=1,r,c,step;
    if(isup(v[0][0])==t[toi(v[0][0])])q.push(tiii{0,0,1});
    while(q.size()&&flag){
        tie(r,c,step)=q.front();
        q.pop();
        for(int k=0;k<4&&flag;k++){
            int r1=r+dr[k],c1=c+dc[k];
            if(r1>=0 && r1<n && c1>=0 && c1<n && v[r1][c1]!=0 && isup(v[r1][c1])==t[toi(v[r1][c1])]){
                if(r1==n-1 && c1==n-1){
                    ans=min(ans,step+1);
                    flag=0;
                }
                v[r1][c1]=0;
                q.push(tiii{r1,c1,step+1});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while(cin>>n){
        ans=oo;
        vector<string> v(n,"");
        for(int i=0;i<n;i++)cin>>v[i];
        for(int i=0;i<1024;i++){
            vector<bool> t(10);
            for(int cur=0,k=i;k;k>>=1)t[cur++]=k&1;
            bfs(v,t,n);
        }
        cout<<(ans!=oo?ans:-1)<<endl;
    }
}

---

12844

---

13185_DPA_Numbers_I

Mon, Jul 18, 2022 3:45 PM

題目簡述:book:

體感難度：★
Browse Problem

• T筆測資。
• 輸入正整數n，設x為n的所有因數總和減去n：
  x=n 輸出 "perfect"
  x<n 輸出 "deficient"
  x>n 輸出 "abundant"

詳解:pencil2: (知識點：國小因數分解)

1~sqrt(n)找因數並相加，注意!當i=sqrt(n)時只加一次。

參考答案

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        int sum=0;
        for(int i=1;i*i<=n;i++)
            if(n%i==0)sum+=(i*i==n)?i:(i+n/i);
        if(sum-n==n)cout<<"perfect"<<endl;
        else if(sum-n<n)cout<<"deficient"<<endl;
        else cout<<"abundant"<<endl;
    }
}

---

13194_DPA_Numbers_II

Mon, Jul 18, 2022 4:45 PM

題目簡述:book:

體感難度：★★★★
Browse Problem

• 承上題
• 只是n很大很大 (2<=n<=10^12)

詳解:pencil2: (知識點：找質數+DFS)

步驟一 找不大於sqrt(10^12)之所有質數

• 埃拉托斯特尼篩法：
  建立數字表並全部設為true
  重複以下操作：
  1. 找到還沒被設為false的最小數字
  2. 將該數字放入質數陣列
  3. 將表中所有該數的倍數設為false
     
     

vector<bool> prime_table(N,1);
vector<int> prime;
void build(){
    prime_table[0]=prime_table[1]=0;
    for(int i=2;i<N;i++){
        if(prime_table[i]){
            prime.push_back(i);
            for(int j=i+i;j<N;j+=i)
                prime_table[j]=0;
        }
    }
}

步驟二 找質因數

利用質數陣列對n質因數分解

vector<pair<int,int>> vec; //pair<質因數,數量>
for(int i=0;n1>1&&i<prime.size();i++){		
    if(n1%prime[i]==0)vec.push_back({prime[i],0});
    while(n1%prime[i]==0){
        n1/=prime[i];
        vec[vec.size()-1].second++;
    }
}
if(n1>1) //n1>1代表n還存在一個大於sqrt(10^12)的質因數
    vec.push_back({n1,1});

步驟三 找因數

用DFS窮舉所有因數 (解答中用回朔法優化)

參考答案

#include<bits/stdc++.h>
#define N 1000010
#define int long long
using namespace std;
vector<bool> prime_table(N,1);
vector<int> prime;
void build(){
    prime_table[0]=prime_table[1]=0;
    for(int i=2;i<N;i++){
        if(prime_table[i]){
            prime.push_back(i);
            for(int j=i+i;j<N;j+=i)
                prime_table[j]=0;
        }
    }
}
int dfs(vector<pair<int,int>>& v,int idx){
    if(idx==v.size()){
        int sum=1;
        for(int i=0;i<v.size();i++)sum*=pow(v[i].first,v[i].second);
        return sum;
    }
    int siz=v[idx].second,ans=0;
    for(int i=0;i<=siz;i++){
        v[idx].second=i;
        ans+=dfs(v,idx+1);
    }
    return ans;
}
signed main(){
    build();
    int t,n,n1,sum;
    cin>>t;
    while(t--){
        cin>>n;
        n1=n;
        vector<pair<int,int>> vec;
        for(int i=0;n1>1&&i<prime.size();i++){
            if(n1%prime[i]==0)vec.push_back({prime[i],0});
            while(n1%prime[i]==0){
                n1/=prime[i];
                vec[vec.size()-1].second++;
            }
        }
        if(n1>1)vec.push_back({n1,1});
        sum=dfs(vec,0);
        if(sum-n==n)cout<<"perfect"<<endl;
        else if(sum-n<n)cout<<"deficient"<<endl;
        else cout<<"abundant"<<endl;
	}
}

---