Table of Contents
A. Extract Numbers
B. Queries about less or equal elements
C. Make Palindrome
D. Area of Two Circles’ Intersection
E. Lomsat gelral
A. Extract Numbers
Solution: Simulate according to the meaning of the question, with many details. It can also be regarded as a double pointer to find a sequence that meets the requirements of the question.
#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include<stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
const int mod = 998244353;
const int N = 1e9 + 10;
const int inf = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
string s;cin>>s;
vector<string>a,b;
int n=s.size();
for(int i=0;i<n;i + + ){
int j=i,st=i;
string t="";bool fl=false;
while((s[j]!=',' & amp; & amp;s[j]!=';') & amp; & amp;j<n) {
if(!(s[j]>='0' & amp; & amp;s[j]<='9')) fl=true;
t + =s[j];j + + ;
}
if(t=="") {
b.push_back(t);
}
else{
if(!fl) {
if(t=="0") a.push_back(t);
else{
if(t[0]!='0') a.push_back(t);
else b.push_back(t);
}
}
else b.push_back(t);
}
i=j;
}
if(s[n-1]==','||s[n-1]==';') b.push_back("");
if(!a.size()) cout<<'-'<<'\\
';
else{
// cout<<a.size()<<'\\
';
cout<<'"';
for(int i=0;i<a.size();i + + ) {
cout<<a[i];
if(i<a.size()-1) cout<<",";
}
cout<<'"'<<'\\
';
}
if(!b.size()) cout<<'-'<<'\\
';
else {
// cout<<b.size()<<'\\
';
cout<<'"';
for(int i=0;i<b.size();i + + ) {
cout<<b[i];
if(i!=b.size()-1) cout<<",";
}
cout<<'"'<<'\\
';
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--) solve();
}
B. Queries about less or equal elements
Solution: Sort the a array and divide it into two parts, and use the upper_bound() function directly.
#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include<stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
const int mod = 998244353;
const int N = 1e9 + 10;
const int inf = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
int n,m;
cin>>n>>m;
vector<int>a(n),b(m);
for(int i=0;i<n;i + + ) cin>>a[i];
for(int i=0;i<m;i + + ) cin>>b[i];
sort(a.begin(),a.end());
for(int i=0;i<m;i + + ){
int pos=upper_bound(a.begin(),a.end(),b[i])-a.begin();
if(pos==m){
cout<<m<<" ";
}else{
cout<<pos<<" ";
}
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--) solve();
}
C. Make Palindrome
Solution: Construction question + greedy. The question gives a string and requires the minimum number of operations to construct the smallest palindrome string in lexicographic order. Each operation can change one character. Since the palindrome string is symmetrical, we can count the number of occurrences of the string. Even numbers are directly divided into lexicographic order, half on the left and half on the right. For odd numbers of occurrences, we can pair them in pairs, add one with an odd number of times, and match the other with an odd number. If the times are reduced by one, then the times are all even numbers and can be used directly. Let’s further classify and discuss the number of characters with an odd number of occurrences. If it is an odd number, there must be one that cannot be matched, so just put one of them in the middle. The rest can be used. What is constructed in this way is the optimal solution.
#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include<stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
const int mod = 998244353;
const int N = 1e9 + 10;
const int inf = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
string s;cin>>s;
int n=s.size();
map<char,int>mp;
for(int i=0;i<n;i + + ) mp[s[i]] + + ;
vector<char>res;
for(char i='a';i<='z';i + + ){
if(mp[i] & amp;1){
res.push_back(i);
}
}
// for(auto t:res){ cout<<t<<" ";}
for(int i=0;i<res.size()/2;i + + ){
mp[res[i]] + + ;
mp[res.size()-1-i]--;
}
string ans="";
if(res.size() & amp;1){
ans + =res[res.size()/2];
}
for(int i='z';i>='a';i--){
ans=string(mp[i]/2,i) + ans + string(mp[i]/2,i);
}
cout<<ans<<'\\
';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--) solve();
}
D. Area of Two Circles’ Intersection
Solution: Calculation of geometry problem board questions, cosine theorem to find the intersection area of circles. (Pay attention to accuracy issues)
#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include<iomanip>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
const int mod = 998244353;
const int N = 1e9 + 10;
const int inf = 0x3f3f3f3f;
const long double Pi=acos(-1.0);
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
void solve()
{
long double x1,y1,r1,x2,y2,r2;
cin>>x1>>y1>>r1>>x2>>y2>>r2;
long double d=sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
//cout<<d<<'\\
';
cout<<fixed<<setprecision(10);
if(d>=r1 + r2){
cout<<0<<'\\
';
return;
}
if(r1 + d<=r2){
cout<<Pi*r1*r1<<'\\
';
return;
}
if(r2 + d<=r1){
cout<<Pi*r2*r2<<'\\
';
return;
}
//cout<<fixed<<setprecision(10);
long double ans=0;
long double a1=acos((r1*r1 + d*d-r2*r2)/(2*r1*d));
//cout<<a1<<'\\
';
ans + =r1*r1*a1;
ans-=r1*sin(a1)*r1*cos(a1);
long double a2=acos((r2*r2 + d*d-r1*r1)/(2*r2*d));
ans + =r2*r2*a2;
ans-=r2*sin(a2)*r2*cos(a2);
cout<<ans<<'\\
';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
solve();
}
E. Lomsat gelral
Solution: Heuristic merging board problem on tree (dsu on tree).
#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include<stack>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
const int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int lowbit(int x) {return x & amp;-x;}
vector<LL>v[N],col(N),siz(N),son(N),cnt(N),ans(N);//siz records the number of nodes in the subtree of the heavy son, son record heavy chain
LL sum,flag,maxc;
void dfs_1(int u,int f){//Heavy chain splitting
siz[u]=1;
for(auto t:v[u]){
if(t==f) continue;
dfs_1(t,u);
siz[u] + =siz[t];
if(siz[t]>siz[son[u]]){//Update heavy chain
son[u]=t;
}
}
}
void count(int u,int f,int val){
cnt[col[u]] + =val;
if(cnt[col[u]]>maxc){
maxc=cnt[col[u]];
sum=col[u];
}
else if(cnt[col[u]]==maxc) sum + =col[u];
for(auto t:v[u]){
if(t==f||t==flag) continue;
count(t,u,val);
}
}
void dfs_2(int u,int f,bool keep){//dsu on tree
//Calculate light chain first
for(auto t:v[u]){
if(t==f||t==son[u]) continue;
dfs_2(t,u,false);
}
//Calculate heavy chain
if(son[u]) {
dfs_2(son[u],u,true);
flag=son[u];
}
count(u,f,1);
flag=0;ans[u]=sum;
//Delete light chain contribution
if(!keep){
count(u,f,-1);
sum=maxc=0;
}
}
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i + + ) cin>>col[i];
int x,y;
for(int i=0;i<n-1;i + + ){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs_1(1,0);
dfs_2(1,0,0);
for(int i=1;i<=n;i + + ) cout<<ans[i]<<" ";
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
solve();
}