標籤: apcs

APCS 2021 9/5

mtmattAPCS, APCS實作題Leave a Comment on APCS 2021 9/5

1. 對聯

  • A : 2, 4字平仄不同 && 2, 6平仄相同
  • B : 第一句最後一字仄，第二句則是平
  • C : 第一二句2, 4, 6 字分別平仄不同

input : 七言對聯 0->平, 1->仄

1
0 0 0 0 1 1 1
1 1 1 1 0 0 0

ouput : 違反ABC哪些個規則就輸出相對應的英文字母(ABC)，若沒違反則輸出 "None"

A

2. 炸彈魔王

遊戲採回合制，回合開始時若魔王位於炸彈上則所有在同一格的魔王會連同炸彈一起消失，所有未消失的魔王會先在腳下放一顆炸彈，再依據方向向量(s, t)移動。移動到邊界外的魔王視為消失。
求所有魔王消失時還有未爆彈的地點數。

n,m,r,c <= 100, k<500, |s,t|<=10

input : 第一行 n, m, k 分別表示地圖長寬以及魔王數，接下來有 k 行每一行都有r, c, s, t 分別表示魔王初始位置座標，以及移動向量。

3 3 2
1 2 0 -1
2 1 1 -2

output:

5

3. 幸運號碼

給一個陣列，依據以下步驟尋找答案。

  1. 找到區間最小值
  2. 依據最小值分為左右兩邊詢問
  3. 選擇區間和較小的一邊作為下個搜索區間
    n<=300000

input : 

6
3 2 1 5 4 7

output:

7

4. 美食

有 n 攤美食和 k 個人，每個人必須吃連續區段的攤位，且菜色不得重複。求最大可以被吃到的攤位數。

n<=1000000, k<=20, nk<=5000000, a[i]<100000

其他限制
50% k=1
100% none

input :

5 1
1 2 3 1 2

output:

3

C++ 基礎題 Q-2-13 無理數的快速冪

mtmattAPCS, APCS325Leave a Comment on C++ 基礎題 Q-2-13 無理數的快速冪

實做好無理數的乘法後就簡單了

#include<bits/stdc++.h>
using namespace std;

const int p=1000000009;
struct number{
    long long x,y;
};
number operator*(number a,number b){
    number c;
    c.x=((a.x*b.x%p)+(2*a.y*b.y%p))%p;
    c.y=((a.x*b.y%p)+(a.y*b.x%p))%p;
    return c;
}

number powerNum(number x,int n){
    if(n==1) return x;
    if(n&1) return x*powerNum(x,n-1);
    number t=powerNum(x,n/2);
    return t*t;
}

int main(){
    int n;
    number a;
    cin>>a.x>>a.y>>n;
    number ans=powerNum(a,n);
    cout<<ans.x<<" "<<ans.y;
    return 0;
}

出處：https://judge.tcirc.tw/ShowProblem?problemid=d022

C++ 基礎題 Q-6-5 二維最大子矩陣

mtmattAPCS, APCS325Leave a Comment on C++ 基礎題 Q-6-5 二維最大子矩陣

擱置了半年，如今終於解開。與 Q-2-12有異曲同工之妙，但複雜度變O(n2m)。

#include<bits/stdc++.h>
using namespace std;
#define r first
#define c second
#define INF 100000000000
typedef long long ll;

ll a[205][205],p[205][205];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            p[i][j]=p[i-1][j]+a[i][j];
        }
    }

    ll ans=0;
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ll psum=0;
            for(int k=0;k<m;k++){
                psum+=p[j][k]-p[i][k];
                if(psum<0) psum=0;
                ans=max(psum,ans);
            }
        }
    }
    cout<<ans;
    return 0;
}

出處：https://judge.tcirc.tw/ShowProblem?problemid=d073