文章目录
- A
- B
- C
- D
- E
- G
A
统计A、B输出
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
void solve() {
int cnt1=0,cnt2=0;
string s;
cin>>s;
for(auto c:s){
if(c=='A') cnt1++;
else cnt2++;
}
if(cnt1>=cnt2){
cout<<"A"<<endl;
}else{
cout<<"B"<<endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
B
只需要判断正方形即可，不是正方形就是三角形。
正方形可以找到第一个行出现的1然后往下找，看是不是行列都是1
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
void solve() {
int n;
cin>>n;
string s[n];
rep(i,0,n-1){
cin>>s[i];
}
int xx=0,yy=0;
rep(i,0,n-1){
bool st=false;
rep(j,0,n-1){
if(s[i][j]=='1'){
xx=i;
yy=j;
st=true;
break;
}
}
if(st){
break;
}
}
// cout<<xx<<' '<<yy<<endl;
auto check=[&](int x,int y){
for(int i=1;i+x<n&&y+i<n;++i){
if(s[x+i][y]!=s[x][y+i]){
return false;
}
}
return true;
};
if(check(xx,yy)){
cout<<"SQUARE"<<endl;
}else{
cout<<"TRIANGLE"<<endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
C
计算每个数字会出现的次数，乘起来就是答案。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
vector<int> get(int n) {
vector<int> res(10, 0);
if(!n) return res;
if(n % 10 < 9) {
res = get(n - 1);
while(n) {
res[n % 10]++;
n /= 10;
}
return res;
}
res = get(n / 10);
for(int i = 0; i < 10; i++) res[i] = res[i] * 10 + n / 10 + (i > 0);
return res;
}
void solve() {
int n;
cin>>n;
vector<int> ans = get(n);
int res=0;
for(int i = 1; i < ans.size(); i++) {
res+=i*ans[i];
}
cout<<res<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
D
用一个multiset存一下，之前的数按位取反的结果。
每次读进来之后在set里面查询，有的话直接删掉，没有的话插入就行。
每次删除会对答案造成-1的贡献。
之前的数按位取反有个简单的技巧：
异或上所有位都是1的数。参考jls的代码。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
void solve() {
int n;
cin>>n;
multiset<int>s;
int ans=n;
auto change=[](int x){
int ans=0;
rep(i,0,30){
int k=x&(1<<i);
if(k){
}else{
ans|=(1<<i);
}
}
return ans;
};
rep(i,1,n){
int val;
cin>>val;
if(s.count(val)){
s.erase(s.find(val));
ans--;
}
else s.insert(change(val));
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
E
赛时找到规律了，但是有个小细节没注意到导致没过
就是每个二次幂取的数是当前的
(
n
+
1
)
2
\frac{(n+1)}{2}
2(n+1)
然后n每次减半。
每个二次幂下都是一个等差数列
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
void solve() {
int n,k;
cin>>n>>k;
int cnt=0;
while(k>(n+1)/2){
k-=(n+1)/2;
n/=2;
cnt++;
}
cout<<((2*k-1)<<cnt)<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
G
树上dp。
f
[
u
]
[
0
∣
1
]
f[u][0|1]
f[u][0∣1]:以u为根的为
S
∣
P
S|P
S∣P时的最小隔板数
转移
f
[
u
]
[
0
]
+
=
m
i
n
(
f
[
v
]
[
0
]
,
f
[
v
]
[
1
]
+
1
)
;
f[u][0]+=min(f[v][0],f[v][1]+1);
f[u][0]+=min(f[v][0],f[v][1]+1);
f
[
u
]
[
1
]
+
=
m
i
n
(
f
[
v
]
[
1
]
,
f
[
v
]
[
0
]
+
1
)
;
f[u][1]+=min(f[v][1],f[v][0]+1);
f[u][1]+=min(f[v][1],f[v][0]+1);
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
void solve() {
int n;
cin>>n;
vector<vector<int>>g(n+1);
rep(i,2,n){
int u;
cin>>u;
g[u].pb(i);
}
string s;
cin>>s;
vector<vector<int>>f(n+1,vector<int>(2));
auto dfs=[&](auto &&dfs, int u)->void{
f[u][0]=f[u][1]=0;
if(s[u-1]=='S') f[u][0]=1e9;
if(s[u-1]=='P') f[u][1]=1e9;
for(auto v:g[u]){
dfs(dfs,v);
f[u][0]+=min(f[v][0],f[v][1]+1);
f[u][1]+=min(f[v][1],f[v][0]+1);
}
};
dfs(dfs,1);
cout<<min({f[1][0],f[1][1]})<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
