B - Modulo Number (atcoder.jp)
移项之后发现就是带余除法的形式，直接取模就可以了。（某sb写了个exgcd）
const int p=998244353,k=1;
typedef long long ll;
ll n;
ll exgcd(int a,int b,ll &x,ll &y){
if(!b){
x=1; y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
scanf("%lld",&n);
ll x,y;
ll d=exgcd(p,k,x,y);
y=y*n/d;
y=(y%p+p)%p;
cout<<y<<endl;
return 0;
}
C - Convex Quadrilateral (atcoder.jp)
用向量坐标判断向量夹角是不是小于平角。
对于三个点A，O，B，其中假设夹角是从A沿逆时针绕向B的，如果∠AOB\(<180^。\) ，就有\(ax*by-ay*bx>0\)。
在这题，只需要以每个点为O点，按照逆时针看每个夹角即可。
int ax,ay,bx,by,cx,cy,dx,dy;
int f1,f2,f3,f4;
int main(){
scanf("%d%d",&ax,&ay); scanf("%d%d",&bx,&by);
scanf("%d%d",&cx,&cy); scanf("%d%d",&dx,&dy);
f1=(bx-ax)*(dy-ay)-(dx-ax)*(by-ay);
f2=(cx-bx)*(ay-by)-(ax-bx)*(cy-by);
f3=(dx-cx)*(by-cy)-(bx-cx)*(dy-cy);
f4=(ax-dx)*(cy-dy)-(cx-dx)*(ay-dy);
if(f1>0 && f2>0 && f3>0 && f4>0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
D - Snuke Panic (1D) (atcoder.jp)
数字三角形模型。
假设f[i][j]表示时刻i且当前位于第j个位置的所有情况，属性是最大值。
很容易可以知道f[i][j]能从f[i-1][j],f[i-1][j+1],f[i-1][j-1]推来。
const int N=1e5+5;
typedef long long ll;
ll w[N][5];
ll f[N][5];
int n;
int main(){
scanf("%d",&n);
int t,x,a;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&t,&x,&a);
w[t][x]+=a;
}
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=N-5;i++){
for(int j=0;j<5;j++){
f[i][j]=f[i-1][j]+w[i][j];
if(j>0)f[i][j]=max(f[i][j],f[i-1][j-1]+w[i][j]);
if(j<4)f[i][j]=max(f[i][j],f[i-1][j+1]+w[i][j]);
}
}
ll ans=0;
for(int i=0;i<5;i++)ans=max(ans,f[N-5][i]);
cout<<ans<<endl;
return 0;
}
E - Throwing the Die (atcoder.jp)
假设f[i]表示还剩下i次机会掷色子可以得到的期望点数，考虑剩下i+1次机会的情况。假设第i+1次的点数为x：
- 如果
x>=f[i]，表示第i+1次掷完，剩下i次的期望点数都不会比x大，即当前就可以直接收手了。 - 如果
x<f[i]，表示第i+1次掷完，剩下i次的期望点数更大，即我们只要继续掷下去就更有可能拿到f[i]点。
const int N=105;
double f[N];
int n;
int main(){
scanf("%d",&n);
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=6;j++){
if(j>=f[i-1])f[i]+=j/6.0;
else f[i]+=f[i-1]/6.0;
}
}
printf("%lf\n",f[n]);
return 0;
}
F - Well-defined Path Queries on a Namori (atcoder.jp)
E_DCC缩点，基环树，染色。
先用边双连通分量缩点来把环上的所有点都缩到一起去，然后分别以环上的每个点为根节点往下dfs染色（不能dfs到环上的点），对于任意两个点，只要他们颜色相同，就仅存在一条简单路径可以互相到达。
const int N=2e5+5,M=2*N;
int n,m;
int e[M],ne[M];
int h[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int dcc_cnt,is_bri[M],id[N];
int col[N],cnt,cyc;
vector<int>dcc[N];
void adde(int x,int y){
e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}
void Tarjan(int u,int in){
dfn[u]=low[u]=++timestamp;
stk[++top]=u;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(!dfn[v]){
Tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
is_bri[i]=is_bri[i^1]=1;
}
}
else if(i != (in^1))low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int y;
dcc_cnt++;
do{
y=stk[top--];
id[y]=dcc_cnt;
dcc[dcc_cnt].push_back(y);
}while(y!=u);
}
}
void dfs(int u,int fa,int c){
col[u]=c;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(v==fa || id[v]==cyc)continue;
dfs(v,u,c);
}
}
int main(){
scanf("%d",&n);
int x,y; memset(h,-1,sizeof(h));
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
adde(x,y), adde(y,x);
}
Tarjan(1,-1);
for(int i=1;i<=dcc_cnt;i++){//找到环所在edcc
if(dcc[i].size()>1){ cyc=i; break;}
}
for(auto k:dcc[cyc]){
dfs(k,0,++cnt);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if(col[x]==col[y])printf("Yes\n");
else printf("No\n");
}
return 0;
}