Educational Codeforces Round 2 个人总结A-E
2024-09-08 17:04:07
Educational Codeforces Round 2
A. Extract Numbers
- 简单的模拟
bool check(string op)
{
if(op.size()==1&&op[0]=='0')
return true;
if(op.size()==0||(op[0]<'1'||op[0]>'9'))
return false;
bool st=false;
for(int i=1;i<op.size();i++)
{
if( !(op[i]>='0'&&op[i]<='9'))
st=true;
}
if(st)
return false;
else return true;
}
void solve()
{
string op; cin>>op;
string t="";
vector<string> a;
int len=op.size();
for(int i=0;i<len;i++)
{
if(op[i]!=','&&op[i]!=';')
t=t+op[i];
else
{
a.pb(t);
t="";
}
}
if(!t.empty())
a.pb(t);
if(op[op.size()-1]==','||op[op.size()-1]==';')
a.pb("");
vector<string> b,c;
for(auto it:a)
{
if(check(it))
b.pb(it);
else
c.pb(it);
}
if(b.size()!=0)
{
cout<<"\"";
len=b.size();
for(int i=0;i<len;i++)
{
cout<<b[i];
if(i!=len-1)
cout<<",";
}
cout<<"\""<<endl;
}
else
cout<<"-\n";
if(c.size()!=0)
{
cout<<"\"";
len=c.size();
for(int i=0;i<len;i++)
{
cout<<c[i];
if(i!=len-1)
cout<<",";
}
cout<<"\""<<endl;
}
else
cout<<"-\n";
return;
}
B. Queries about less or equal elements
- 二分查找板子
vector<LL> a,b;
void solve()
{
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x; cin>>x;
a.pb(x);
}
sort(all(a));
for(int i=1;i<=m;i++)
{
int x; cin>>x;
b.pb(x);
}
for(int i=0;i<m;i++)
{
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(a[mid]<=b[i]) l=mid;
else r=mid-1;
}
if(l==0&&b[i]<a[l])
cout<<0<<" ";
else
cout<<l+1<<" ";
}
cout<<endl;
return;
}
C. Make Palindrome
大意：输出使 s 为回文串，在操作次数最少的情况下，s 的字典序最小的字符串
根据回文串的性质，若不是回文串，即有一个或多个字母个数为奇数，为使操作次数最少，即将这些单个字母取出来，有区间 \(b[l,...r]\)从两端进行修改操作，修改操作为 \(b[r]=b[l]\) \((l<r)\)
将 \(b\) 放回 \(s\)，重新构造一下就出来了
int cnt[30],n;
string op;
vector<int> b;
void solve()
{
cin>>op; n=op.size();
for(int i=0;i<n;i++)
cnt[int(op[i]-'a'+1)]++;
for(int i=1;i<=26;i++)
if(cnt[i]%2==1)
{
cnt[i]--;
b.pb(i);
}
int l=0,r=b.size()-1;
while(l<r)
b[r]=b[l],l++,r--;
for(auto it:b)
cnt[it]++;
string ans="";
char t;
for(int i=1;i<=26;i++)
{
int k=cnt[i]/2;
if(cnt[i]%2==1)
t=char('a'+i-1);
while(k--)
ans.pb(char('a'+i-1));
}
string res=ans;
reverse(all(res));
cout<<ans;
if(n%2==1)
cout<<t;
cout<<res<<endl;
return;
}
D. Area of Two Circles' Intersection
- 高中数学知识，用到了正弦定理和余弦定理，然后可以试着去做
- 这题WA34是由于精度原因，计算几何题要避免浮点数的子运算或加法
long double xa,ya,ra,xb,yb,rb;
void solve()
{
cin>>xa>>ya>>ra>>xb>>yb>>rb;
if(ra>rb)
{
swap(xa,xb);
swap(ya,yb);
swap(ra,rb);
}
long double len=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
if(ra+rb<len)
cout<<0<<endl;
else if(rb>=len+ra)
{
long double ans=ra*ra*pi;
cout<<setprecision(10)<<ans<<endl;
}
else
{
long double ang1=2.0*acos((len*len+rb*rb-ra*ra)/(2.0*len*rb));
long double ang2=2.0*acos((len*len+ra*ra-rb*rb)/(2.0*len*ra));
long double ans=ang1*rb*rb/2.0+ang2*ra*ra/2.0-0.5*sin(ang1)*rb*rb-0.5*sin(ang2)*ra*ra;
cout<<setprecision(10)<<ans<<endl;
}
return;
}
E. Lomsat gelral
是一道很入门的dsu，去找dls课看，或者oiwiki
// AC one more times
////////////////////////////////////////INCLUDE//////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
/////////////////////////////////////////DEFINE//////////////////////////////////////////
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define inf64 0x3f3f3f3f3f3f3f3f
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<long long,long long> PLL;
////////////////////////////////////////CONST////////////////////////////////////////////
const int inf = 0x3f3f3f3f;
const int maxn = 2e6 + 6;
const double eps = 1e-8;
///////////////////////////////////////FUNCTION//////////////////////////////////////////
template<typename T>
void init(T q[], int n, T val){ for (int i = 0; i <= n; i++) q[i] = val; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
bool cmp(int c, int d) { return c > d; }
//inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
LL get_quick_mod(LL a,LL b,LL p){ LL ans=1%p;while(b){ if(b&1) {ans=ans*a%p;} a=a*a%p,b>>=1; } return ans; }
const int mod = 1e9+7;
const int N = 1e5+10;
const int M = 1e6+10;
int n,c[N],sz[N],big[N],id[N],l[N],r[N],tot;
vector<int> e[N];
LL cnt[N],maxcnt,sumcnt,ans[N];
void dfs1(int u,int fa)
{
l[u]=++tot;
id[tot]=u;
sz[u]=1;
big[u]=-1;
for(int v:e[u])
{
if(v==fa) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(big[u]==-1||sz[v]>sz[big[u]])
big[u]=v;
}
r[u]=tot;
}
void add(int x)
{
x=c[x];
cnt[x]++;
if(cnt[x]>maxcnt) maxcnt=cnt[x],sumcnt=0;
if(cnt[x]==maxcnt) sumcnt+=x;
}
void del(int x)
{
x=c[x];
cnt[x]--;
}
void dfs2(int u,int fa,bool st)
{
for(int v:e[u])
if(v!=fa&&v!=big[u])
dfs2(v,u,false);
if(big[u]!=-1)
dfs2(big[u],u,true);
for(int v:e[u])
{
if(v!=fa&&v!=big[u])
for(int x=l[v];x<=r[v];x++)
add(id[x]);
}
add(u);
ans[u]=sumcnt;
if(!st)
{
maxcnt=0;sumcnt=0;
for(int x=l[u];x<=r[u];x++)
del(id[x]);
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<n;i++)
{
int u,v; cin>>u>>v;
e[u].pb(v); e[v].pb(u);
}
dfs1(1,0);
dfs2(1,0,false);
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
return;
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
// 特殊输入 请注释上方，如__int128等
int TC = 1;
//cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
最新文章
- 为什么大家都用i标签<i></i>用作小图标?
- type="file" 选择图片后预览
- 读javascript高级程序设计13-JSON
- gdb 7.11
- Linux 卸载Oracle 11G
- [Codeforces137A]Postcards and photos（模拟）
- 尝试设计LFSR加密器，并用CAP4验证随机性
- 【转】C#读取文件时的共享方式
- Spring整合Quartz实现动态定时器
- [Cycle.js] Customizing effects from the main function
- linux中patch命令 -p 选项
- hibernate某些版本（4.3)下报错 NoSuchMethodError: javax.persistence.Table.indexes()
- {key}面向对象程序设计-C++ polymorphism 【第十三次上课笔记】
- Acquire and Release Semantics
- CF417D--- Cunning Gena(序列+像缩进dp)
- mxnet框架样本，使用C++接口
- ORALCE EBS ALERT 初体验
- 断网环境，Python环境迁移
- vue.js 自定义事件
- promise.all方法合并请求接口的两个值