传送门：https://atcoder.jp/contests/abc168/tasks
A
#include<bits/stdc++.h>
using namespace std;
int main(){
int a; cin>>a;
int t=a%10;
if(t==2 || t==4 || t==5 || t==7 || t==9) puts("hon");
else if(t==0 || t==1 || t==6 || t==8) puts("pon");
else puts("bon");
return 0;
}
B
#include<bits/stdc++.h>
using namespace std;
int main(){
int k; string s; cin>>k>>s;
if(s.size()<=k) cout<<s<<endl;
else{
for(int i=0; i<k; i++) cout<<s[i];
puts("...");
}
return 0;
}
C
余弦定理。
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1), eps=1e-12;
double deg(double x){
return 1.0*x/180*pi;
}
int main(){
double a, b, h, m;
cin>>a>>b>>h>>m;
double ang1=deg(6)*m, ang2=deg(30)*(m/60+h);
double dt=fabs(ang1-ang2);
if(dt>pi+eps) dt=2*pi-dt;
// cerr<<ang1/pi*180<<' '<<ang2/pi*180<<endl;
double res=sqrt(a*a+b*b-2*a*b*cos(dt));
printf("%.12lf", res);
return 0;
}
D
注意到要找最短路，直接 (bfs) 即可。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=1e5+5, M=N<<2;
struct node{
int to, next;
}e[M];
int h[N], tot;
void add(int u, int v){
e[tot].to=v, e[tot].next=h[u], h[u]=tot++;
}
int n, m;
bool vis[N];
int res[N];
int q[N], tt=-1, hh=0;
void bfs(){
q[++tt]=1;
vis[1]=true;
while(tt>=hh){
int hd=q[hh++];
for(int i=h[hd]; ~i; i=e[i].next){
int go=e[i].to;
if(!vis[go]){
vis[go]=true;
q[++tt]=go;
res[go]=hd;
}
}
}
}
int main(){
memset(h, -1, sizeof h);
read(n), read(m);
rep(i,1,m){
int u, v; read(u), read(v);
add(u, v), add(v, u);
}
bfs();
rep(i,1,n) if(!vis[i]){
puts("No");
return 0;
}
puts("Yes");
rep(i,2,n) cout<<res[i]<<endl;
return 0;
}
E
题目的意思是：给出 (n) 条向量，然后选择向量组（也就是向量集合的子集），使得向量组内没有任何两个向量是正交的，求方案数。
首先用 (gcd) 将极角相等的向量化成统一的形式，然后丢进桶（map<PII, int> 实现）中，然后就是利用组合计数的乘法原理，对于正交的每一组，设组中第一个元素有 (x) 个，第二个元素有 (y) 个，那么这一组的贡献为 (2^(x + y -1)) ，然后依次将每一组的贡献乘起来即可。
注意两个点：
- 空集不计入贡献，记得 (-1) ，同时出现减法的时候注意取 (mod) 的方法。
- 可能会出现向量为 ((0, 0)) 的情况，注意到取了它之后就不能取其他组了，所以它对方案数的贡献就是 ((0, 0)) 的个数。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
#define x first
#define y second
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=2e5+5, mod=1e9+7;
int n;
PII e[N];
int gcd(int a, int b){
return b? gcd(b, a%b): a;
}
map<PII, int> buc;
int add(int a, int b){
return ((a+b)%mod+mod)%mod;
}
int fpow(int x, int p){
int res=1;
for(; p; p>>=1, x=x*x%mod)
if(p&1) res=res*x%mod;
return res;
}
set<PII> vis;
int cnt;
signed main(){
read(n);
rep(i,1,n){
int a, b; read(a), read(b);
if(!a && !b){
cnt++;
continue;
}
else {int g=gcd(a, b); a/=g, b/=g; if(a<0) a*=-1, b*=-1;} // promise that a is not nega
e[i]={a, b};
buc[e[i]]++;
}
int res=1;
for(auto i: buc){
int a=i.x.x, b=i.x.y;
swap(a, b);
if(a<0) a*=-1; else b*=-1;
PII j={a, b};
if(vis.count(i.x) || vis.count(j)) continue;
int x=buc[i.x]; int y=buc[j];
res=(res*((fpow(2, x)+fpow(2, y)-1)%mod))%mod;
vis.insert(i.x), vis.insert(j);
}
res=add(res, cnt);
res=add(res, -1);
cout<<res<<endl;
return 0;
}
F
思路大概就是离散化压缩图片，然后 bfs ，代码会补的