題目目錄
- A. A+B Problem
- B. 77777
- C. Merge
- D. 魔法少女:承
- E.學妹的任務
- F. AKIE's Penalty
- G. A-B Problem
- H. 翻轉佇列
- I. 魔法少女:轉
- J. 挑選佇列
- K. 魔法少女:合
- L. 神奇的轉盤
- M. AAO
- N. 來自異世界的巧克力
- O. hina的迷宮
若發現錯誤或疑問,聯系QQ:1098509291 指正/說明,
A. A+B Problem
題意: 找一個最小的整數 K ( 2 ≤ K ≤ 9 ) K(2\leq K \leq 9) K(2≤K≤9)滿足 ( a + b ) 10 = ( n ) K (a+b)_{10}=(n)_K (a+b)10?=(n)K?,找不到則輸出 ? 1 -1 ?1
思路: 模擬,列舉 2 2 2到 9 9 9進制,判斷 n n n是否可以是這個進制的數,如果可以就把 n n n轉化成 10 10 10進制數判斷是否與 a + b a+b a+b相等,
//A+B Problem Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int a,b;
string n;
int main(){
cin>>a>>b>>n;
for(int i=2;i<=9;i++){
int sum=0;
for(int j=n.length()-1,k=1;j>=0;j--,k*=i){
if(n[j]-'0'>=i){sum=-1;break;}
sum+=k*(n[j]-'0');
}
if(sum==a+b){
cout<<i;
return 0;
}
}
cout<<-1;
}
B. 77777
題意: 問所給的小寫串 S S S中是否能找到一個子串,其中至少有一個字母的出現次數恰好等于 7 7 7
思路: 貪心,遍歷一遍串 S S S,只要整個串里有一個字母出現的次數 ≥ 7 \geq 7 ≥7,就一定能找到一個合法的子串使得其中至少有一個字母的出現次數恰好等于 7 7 7,
//77777 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int n,cnt[26];
string s;
int main(){
cin>>n>>s;
for(int i=0;i<n;i++)cnt[s[i]-'A']++;
for(int i=0;i<26;i++)
if(cnt[i]>=7){
printf("YES");
return 0;
}
printf("NO");
}
C. Merge
題意: 給 n n n張帶權值的卡牌,每次可執行一個操作:選一張卡牌,讓它相鄰的一張卡牌加或減所選卡牌的權值,并把所選卡牌刪掉,求最后剩余的一張卡牌的最大權值,
思路: 貪心,
1° 若至少有一張卡牌權值 ≥ 0 \geq0 ≥0,我們可以讓這張牌加上所有正權值卡牌,減去所有負權值卡牌,那么答案應該是所有卡牌的權值絕對值之和
2° 若所有卡牌權值都 < 0 <0 <0,此時至少有一張卡牌的權值需要取負的貢獻,其余卡牌可以取正的貢獻(即絕對值),也就是說我們應該找到一張卡牌,讓它去減其他所有卡牌,所以要最大化最終權值,應該找權值最大的卡牌,去減其他所有卡牌,答案也就是所有卡牌的權值絕對值之和 - 最大的卡牌權值*2
//Merge Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+7;
int n;
LL ans,x,k=-1e9-1;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&x);
ans+=(x>0?x:-x);
k=max(k,x);
}
if(n==1)cout<<k;
else if(k>=0)cout<<ans;
else cout<<ans+k+k;
}
D. 魔法少女:承
題意: 給定每顆高、低純度結晶的回復理性值和純粹度,找一種使用高、低純度結晶的個數,使得理性值回滿,平均純粹度 ≥ 60 % \geq60\% ≥60%,盡可能節約高純度結晶,其次節約低純度結晶,
思路: 兩層for回圈列舉使用兩種結晶的個數,判斷是否合法,更新最小值,
//魔法少女:承 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int T,a1,b1,a2,b2;
int main(){
cin>>T;
while(T--){
cin>>a1>>b1>>a2>>b2;
int ans1=INT_MAX,ans2=INT_MAX;
for(int i=0;i<=100;i++)
for(int j=0;j<=100;j++)
if(i*a1+j*a2>=100&&(i*b1+j*b2)/(i+j)>=60){
if(i<ans1||(i==ans1&&j<ans2)){
ans1=i;
ans2=j;
}
}
printf("%d %d\n",ans1,ans2);
}
}
E.學妹的任務
題意: 依次拼接字串,對當前已拼接的字串的后綴和下一個待拼接的字串的前綴去重再拼接,
思路: 每次拼接時,列舉下一個待拼接的字串的所有前綴,用string中的substr函式判斷這個前綴是否是已拼接的字串的后綴,如果是,更新最大重疊長度,然后暴力拼接非重疊部分,
//學妹的任務 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int n;
string s[107],ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
ans=s[1];
for(int i=2;i<=n;i++){
int l0=ans.length(),l1=s[i].length(),k=0;
for(int j=l1;j;j--){
if(l0-j<0)continue;
if(s[i].substr(0,j)==ans.substr(l0-j,j)){
k=j;
break;
}
}
for(int j=k;j<l1;j++)ans+=s[i][j];
}
cout<<ans;
}
F. AKIE’s Penalty
題意: 給定N個題的提交次數和通過時間,若通過時間 T i Ti Ti為正,則最后一次提交正確,若通過時間 T i Ti Ti為負,則本題未通過,每次錯誤提交的罰時為20,計算所有通過題目的總罰時,
思路: 若 T i Ti Ti為正,此題罰時為 ( K i ? 1 ) ? 20 + T i (Ki-1)*20+Ti (Ki?1)?20+Ti,否則罰時為0,累加即可,
//AKIE's Penalty Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=107;
int n,ans,k[N],t;
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&k[i]);
for(int i=1;i<=n;i++){
scanf("%d",&t);
if(t>=0)ans+=20*(k[i]-1)+t;
}
printf("%d",ans);
}
G. A-B Problem
題意: 輸入兩個數,輸出A-B,
思路: …[組織語言中.jpg]
//A-B Problem Standard Code [C++]
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a<<"-"<<b;
}
H. 翻轉佇列
題意: 給兩個只包含 0 / 1 0/1 0/1的串 A , B A,B A,B,每次可以執行操作:從A串中選一個 1 1 1作為中心,將其相鄰的前一個位置的數和后一個位置的數取反( 0 0 0變成 1 1 1, 1 1 1變成 0 0 0),但開頭和結尾位置上的 1 1 1不能被作為中心,問是否能由 A A A串經過若干次操作(或零次)變為 B B B串,
思路:
假設 A A A串是 1101 1101 1101, B B B串是 0111 0111 0111,我們對它們分別按位取異或前綴和,
可以得到前綴和陣列 S U M A SUM_A SUMA?: 1001 1001 1001, S U M B : 0101 SUM_B: 0101 SUMB?:0101
我們選定 A A A串中第二個 1 1 1為中心,進行相鄰取反操作,是將其前面第一個數和其后面第一個數取反, A A A會變為 0111 0111 0111,此時 S U M A SUM_A SUMA?會變為 0101 0101 0101
可以看出來,如果我們以位置 i i i為中心,對 i ? 1 i-1 i?1和 i + 1 i+1 i+1取反,對前綴和陣列的影響是: S U M [ i ? 1 ] SUM[i-1] SUM[i?1]取反, S U M [ i ] SUM[i] SUM[i]取反,對前綴和陣列中的其余值其實沒有影響,由于 A A A串中 i i i 位置是選擇的中心,所以它這一位肯定是 1 1 1,所以 S U M A SUM_A SUMA?陣列中 S U M A [ i ? 1 ] SUM_A[i-1] SUMA?[i?1]和 S U M A [ i ] SUM_A[i] SUMA?[i]一定不同,那么這兩位,肯定一個是 1 1 1、一個是 0 0 0,給它們取反,也就是等同于做了交換,
所以,經過若干次操作后,前綴和陣列中的 0 0 0和 1 1 1的數量不會改變,
并且因為 A A A串的首尾的 1 1 1不能被選為操作中心,所以不管怎么操作, S U M A [ n ] SUM_A[n] SUMA?[n]都不會改變,
所以判斷兩個串的異或前綴和陣列中 0 0 0和 1 1 1的數量對應一致,并且兩個01串的位異或和相等,那么一定可以通過給 A A A串的異或前綴和陣列做若干次交換,使其與 B B B的異或前綴和陣列一致,也就把 A A A變得與 B B B串一致了,即輸出yes,
注意: 由于記憶體限制為1.5M,所以不可以開2×106長度的int陣列,但好像可以開一個相同長度的bitset(未測驗),題解代碼未使用陣列,
//翻轉佇列 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int n,sum1,cnt1,sum2,cnt2;
int main(){
cin>>n;
char x;
for(int i=1;i<=n;i++){
while(x=getchar(),x!='0'&&x!='1');
sum1^=(x=='1');
cnt1+=(sum1==1);
}
for(int i=1,x;i<=n;i++){
while(x=getchar(),x!='0'&&x!='1');
sum2^=(x=='1');
cnt2+=(sum2==1);
}
if(cnt1==cnt2&&sum1==sum2)printf("yes");
else printf("no");
}
I. 魔法少女:轉
題意: 找一種五個亡者之怒的使用順序并指定它們的打擊魔獸,使得所有魔獸都被消滅,
思路: 深度優先搜索(dfs),搜索每個魔獸被使用的亡者之怒,若已經被消滅就搜索下一個魔獸,找到答案就輸出即可,
//魔法少女:轉 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int T,hp[4],a[6],ans[6],flag;
void dfs(int k,int damage){
if(flag)return;
if(k>3){
for(int i=1;i<=5;i++)printf("%d%c",ans[i]," \n"[i==5]);
flag=1;
return;
}
if(damage>=hp[k]){
dfs(k+1,0);
return;
}
for(int i=1;i<=5;i++)
if(!ans[i]){
ans[i]=k;
dfs(k,damage+a[i]);
ans[i]=0;
}
}
int main(){
cin>>T;
while(T--){
flag=0;
for(int i=1;i<=3;i++)cin>>hp[i];
for(int i=1;i<=5;i++)cin>>a[i];
dfs(1,0);
}
}
J. 挑選佇列
題意及思路: Provided By 楊熠辰
本題大意為在
1
?
n
1-n
1?n 中挑選出
3
3
3 個數使得兩兩互質或兩兩不互質的方案數,
我們考慮一個含有 n n n 個點的無向圖,如果兩個數互質,那么就在這兩個數之間連邊,這樣的話,這題本質上就是求圖上三個點的個數,并且要求要么兩兩連邊,要么兩兩不連邊,
由于直接做不是很好做,所以我們考慮容斥,用所有的三元組減掉非法的三元組來求答案,
非法的三元組無非只有兩種情況,一種是三個點之間只有一條邊,另一種是三個點之間有兩條邊,如下圖:

對于圖 1 1 1,我們考慮點 1 1 1,我們可以發現它與其他的兩個點連接且僅連接了一條邊,即點 1 1 1 與點 2 2 2 有連邊卻與點 3 3 3 沒有連邊,對于點 2 2 2 也是,
我們發現圖 2 2 2 也有這個性質,即三元組中恰好存在兩個點,這兩個點與除了它自己之外的點恰好連了一條邊,另一條沒有連邊,
于是,我們可以對于每個點,統計一下它的度數,對于點 i i i,求所有點的 d [ i ] × ( n ? d [ i ] ? 1 ) d[i] \times (n - d[i] - 1) d[i]×(n?d[i]?1) 之和,然后把結果除 2 2 2 即是不合法的三元組數,
所以我們下一步只需要求出每個點的度數即可,根據題意,對于點 i i i,有
d
[
i
]
=
∑
j
=
1
n
[
gcd
?
(
i
,
j
)
=
1
]
=
∑
d
∣
i
μ
(
d
)
?
n
d
?
d[i] = \sum_{j = 1}^n[\gcd(i, j) = 1] = \sum_{d|i}\mu(d)\lfloor\frac nd\rfloor
d[i]=j=1∑n?[gcd(i,j)=1]=d∣i∑?μ(d)?dn??
但是如果采用列舉因數的方式求
d
[
i
]
d[i]
d[i] 其最終時間復雜度為
O
(
n
n
)
O(n\sqrt n)
O(nn
?),所以我們更改列舉方式,對于一個因數
d
d
d,我們將
μ
(
d
)
?
n
d
?
\mu(d)\lfloor\frac nd\rfloor
μ(d)?dn?? 加到其倍數上,這樣可以在
n
log
?
n
n\log n
nlogn 的時間復雜度內解決此問題,
//挑選佇列 Standard Code [C++]
#include <bits/stdc++.h>
const int MAXN = 2e6 + 5;
int mu[MAXN], prime[MAXN], notprime[MAXN], n, cnt;
long long f[MAXN];
void Shaker() {
notprime[1] = mu[1] = 1;
for(int i = 2; i <= n; i++) {
if(!notprime[i]) prime[cnt++] = i, mu[i] = -1;
for(int j = 0; j < cnt && i * prime[j] <= n; j++) {
notprime[i * prime[j]] = 1;
if(i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
}
long long cn3(int n) {
return 1LL * n * (n - 1) * (n - 2) / 6;
}
int main() {
long long ans = 0;
scanf("%d", &n);
Shaker();
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j += i)
f[j] += n / i * mu[i];
f[1]--;
for(int i = 1; i <= n; i++) ans += 1LL * f[i] * (n - f[i] - 1);
ans = cn3(n) - ans / 2;
printf("%lld\n", ans);
return 0;
}
K. 魔法少女:合
題意: 分別給定兩棵樹的所有連邊,判斷兩棵樹是否完全相同(節點、連邊都相同),
思路: 分別對兩棵樹每條邊的兩個點升序排序,對所有邊按照兩端點雙關鍵字排序,然后判斷兩棵樹的邊對應相等即可,
//魔法少女:合 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;
int n;
pair<int,int>a[N],b[N];
int main(){
cin>>n;
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
a[i]=make_pair(x,y);
}
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
b[i]=make_pair(x,y);
}
sort(a+1,a+n);
sort(b+1,b+n);
int flag=1;
for(int i=1;i<n&&flag;i++){
if(a[i]!=b[i])flag=0;
}
if(flag)cout<<"RED PILL";
else cout<<"BLUE PILL";
}
L. 神奇的轉盤
題意: 互動題,有一個 2 ? 2 2*2 2?2的轉盤亂序填入了 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4四個數,每次可以詢問 x x x n n n,代表位于 x x x位置上的數是否為 n n n,系統會回答,轉盤會在每次詢問前順時針旋轉 90 ° 90° 90° ,要求在 6 6 6次詢問以內,確定當前轉盤狀態并輸出,
思路:
假設起始轉盤是:[數字代表轉盤中存的數字]
2 2 2 3 3 3
1 1 1 4 4 4
(1) 第一次詢問前變為:
1 1 1 2 2 2
4 4 4 3 3 3
(2) 第二次詢問前變為:
4 4 4 1 1 1
3 3 3 2 2 2
(3) 第三次詢問前變為:
3 3 3 4 4 4
2 2 2 1 1 1
對于這個起始轉盤,我們可以通過前三次詢問本轉盤中數字 1 1 1 (標紅色的位置)所出現的位置,分別詢問它是否是 1 / 2 / 3 1/2/3 1/2/3,從而確定標紅位置是幾,
可以看出(1)、(2)、(3)中數字 1 1 1所在的位置分別是位置1,位置2,位置3
所以我們第一次詢問 1 1 1 1 1 1,第二次詢問 2 2 2 2 2 2,第三次詢問 3 3 3 3 3 3,就可以確定標紅色的位置存的數是幾,
同理,確定了第一個數,在用剩下的三個數中的任意兩個去測驗 2 2 2次**本轉盤中數字 2 2 2接下來出現的兩個位置,可以確定本轉盤中數字 2 2 2**的位置存的數是幾,
最后再用剩下的兩個數去測驗本轉盤中數字3接下來出現的一個位置,確定本轉盤中數字3的位置存的是幾,
所以詢問恰好 3 + 2 + 1 3+2+1 3+2+1次即可確定轉盤內容,并輸出當前轉盤內容,
以上程序可以用一個函式實作詢問,
//神奇的轉盤 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int flag[5],a[3][3];
void query(int x,int y,int start,int end){
int sum=0;
for(int i=1;i<=4;i++)
if(!flag[i])sum+=i;
for(int i=start,j=1,k;i<=end;i++,j++){
while(flag[j])j++;
cout<<i<<" "<<j<<endl;
sum-=j;
cin>>k;
if(k==1)a[x][y]=j,flag[j]=1;
}
if(!a[x][y])a[x][y]=sum,flag[sum]=1;
}
int main(){
query(1,2,1,3);
query(2,2,1,2);
query(2,1,4,4);
query(1,1,2020,1024);//后兩個引數任意填的,只要進函式之后不執行回圈即可
cout<<0<<endl;
cout<<a[1][1]<<" "<<a[1][2]<<"\n"<<a[2][1]<<" "<<a[2][2];
}
M. AAO
題意: 新創語言,有 n n n個數 [ 1 , 2 , . . . , n ] [1,2,...,n] [1,2,...,n],但輸入缺失了一個數(只輸入 n ? 1 n-1 n?1個數),要求找出缺失的數,
思路: 做法很簡單,就是計算 1 + 2 + . . . + n 1+2+...+n 1+2+...+n的值,減去所有輸入的數,即是缺失的數,難點在于要用新創語言給定的陳述句做,建議用C++11自帶的
cout<<R"(...)";
陳述句輸出所有新語言的句子,具體寫法如下:
//AAO Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<R"(
Initial n
Yes, BangDream
Hey, Y.O.L.O!!!!! n
Initial sum
ROKIROKIROLL n
Yes, BangDream
Initial n
Please don't say "You are lazy" 1
Yes, BangDream
Initial x
Yes, BangDream
A to Z! A to Z! n
Hey, Y.O.L.O!!!!! x
Initial sum
ROKIROKIROLL n
Please don't say "You are lazy" x
Yes, BangDream
Initial n
Please don't say "You are lazy" 1
Yes, BangDream
tenkao
go go go for it! sum
)";
}
N. 來自異世界的巧克力
題意: 給一個數 n n n,要求把它分成 x x x個正奇數 + y y y個正偶數,使得這 x x x個奇數和 y y y個偶數的和等于 n n n,注意,沒有要求所分的數各不相同,
思路:
1° 偶數不會改變奇偶性,奇數個奇數的和仍然是奇數,偶數個奇數的和是偶數,所以我們可以先根據 n n n的奇偶性和 x x x的奇偶性判斷是否可以分,
2° x x x個正奇數 + y y y個正偶數的和的最小值應該是 x x x個 1 1 1和 y y y個 2 2 2相加,所以我們可以把 x + 2 ? y x+2*y x+2?y 的值與 n n n比較,若 x + 2 ? y > n x+2*y > n x+2?y>n,顯然沒法分,
所以,判斷完可以分之后,我們可以先把 n n n分出來 x x x個 1 1 1和 y y y個 2 2 2,剩下的值肯定是一個偶數,我們可以把剩余值加到任意分出來的數上,輸出即可,
//來自異世界的巧克力 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;
LL n,x,y;
void solve(){
scanf("%lld%lld%lld",&n,&x,&y);
if((n%2==0&&x%2==1)||(n%2==1&&x%2==0)||x+2LL*y>n){
printf("NO\n");
return;
}
printf("YES\n");
n-=x+2LL*y;
for(int i=1;i<=x;i++)printf("1%c"," \n"[i==x]);
for(int i=1;i<y;i++)printf("2 ");
printf("%lld\n",n+2);
}
int main(){
cin>>t;
while(t--)solve();
}
O. hina的迷宮
題意: 給一個字符矩陣的迷宮,其中有已存在的墻壁(不能通過),人物可以向 8 8 8個相鄰的方向走(不可以走到迷宮外),問是否有方案設定不多于 k k k個墻壁,使得人物不能從左上角走到右下角,
思路: 在起點的右方、下方、右下方設定字串即可,設定的時候判斷一下原來是否存在墻壁,注意,如果n * m=2 * 2,無論如何設定墻壁,都無法阻擋人物到達右下角(因為終點不能設定墻壁,直接從起點往右下方走一步即可到達),
//hina的迷宮 Standard Code [C++]
#include<bits/stdc++.h>
using namespace std;
int T,n,m,k;
char s[57][47];
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
if(n*m==4)return (void)puts("NO");
puts("YES");
int cnt=(s[1][2]=='.')+(s[2][1]=='.')+(s[2][2]=='.');
cout<<cnt<<"\n";
if(s[1][2]=='.')cout<<"1 2\n";
if(s[2][1]=='.')cout<<"2 1\n";
if(s[2][2]=='.')cout<<"2 2\n";
}
int main(){
cin>>T;
while(T--)solve();
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/226967.html
標籤:其他
上一篇:最新出爐!3輪技術面和1輪Hr面拿下頭條offer,終圓我大廠夢
下一篇:[C]你叫我么么噠三子棋
