https://pintia.cn/problem-sets/1703372159713652736/exam/problems/type/7
I Pa?sWorD
分析：
每个字符必须得至少出现一次 立马想到容斥
转移就顺序转移就好 不过有空间限制 因为当前位置的所有状态都由上一个位置转移 所以我们用个滚动数组就好
含有字符串的写起来就是有点麻烦
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
void solve();
const int maxn=1e5+5;
const ll mod=998244353;
int n;
ll dp[2][65];
ll dpsum[2];
ll ans=0;
string s;
int ver(char x){
if('a'<=x&&x<='z')return x-'a'+1;
if('A'<=x&&x<='Z')return x-'A'+27;
if('0'<=x&&x<='9')return x-'0'+53;
return 0;
}
int pd(char x,int num){
if(x=='?')return 1;
if('A'<=x&&x<='Z'){
if(num==ver(x))
return 1;
}
if('0'<=x&&x<='9'){
if(num==ver(x))
return 1;
}
if('a'<=x&&x<='z'){
if(num==ver(x))
return 1;
char tp=x-'a'+'A';
if(num==ver(tp))
return 1;
}
return 0;
}
int main(){
int T;T=1;
while(T--)solve();
return 0;
}
vector<int>q;
void solve(){
cin>>n>>s;
for(int K=1;K<1<<3;K++){
q.clear();
if(K&1==1)for(int i=1;i<=26;i++)q.push_back(i);
if((K>>1)&1)for(int i=27;i<=52;i++)q.push_back(i);
if((K>>2)&1)for(int i=53;i<=62;i++)q.push_back(i);
int m=q.size();
for(int i=0;i<65;i++)dp[0][i]=0;
dpsum[0] = dpsum[1]=0;
if(s[0]=='?')for(int i=0;i<m;i++)dp[0][q[i]]=1;
else if('A'<=s[0]&&s[0]<='Z'){
int sig = ver(s[0]);
for(int i=0;i<m;i++)
if(q[i]==sig){
dp[0][sig]=1;
break;
}
}else if('0'<=s[0]&&s[0]<='9'){
int sig = ver(s[0]);
for(int i=0;i<m;i++)
if(q[i]==sig){
dp[0][sig]=1;
break;
}
}
else {
int sig = ver(s[0]);
for(int i=0;i<m;i++)
if(q[i]==sig){
dp[0][sig]=1;
break;
}
char tp=s[0]-'a'+'A';
sig=ver(tp);
for(int i=0;i<m;i++)
if(q[i]==sig){
dp[0][sig]=1;
break;
}
}
for(int i=1;i<=65;i++)
dpsum[0]+=dp[0][i];
int id,pre;
for(int i=2;i<=n;i++){
if(i&1)id=0,pre=1;
else id=1,pre=0;
dpsum[id]=0;
for(int j=0;j<m;j++){
if(pd(s[i-1],q[j])){
dp[id][q[j]]=(dpsum[pre]-dp[pre][q[j]]+mod)%mod;
dpsum[id]=(dpsum[id]+dp[id][q[j]])%mod;
}
else {
dp[id][q[j]]=0;
}
}
}
// cout<<"K="<<K<<" sum="<<dpsum[id]<<endl;
int res=__builtin_popcount(K);
if(res&1)ans=(ans+dpsum[id])%mod;
else ans=(ans-dpsum[id]+mod)%mod;
}
cout<<ans<<endl;
}
G Spanning Tree
分析：
每次合并的时候 如果两个集合之间没有目标连边 那么直接就是0
如果有目标连边 设两个集合的大小分别为sz1，sz2 那么概率是1/(sz1×sz2)
现在问题转化为如何快速判断两个集合是否有没有目标连边
因为这条边是在树上 所以两个集合一定是父子关系 所以只需要判断深度小的集合的父亲节点是否在深度大的集合上
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int N = 1000005;
const ll mod=998244353;
int nextt[N << 1], to[N << 1], head[N], cnt = 0;
void add(int x, int y) {
nextt[++cnt] = head[x];
to[cnt] = y; head[x] = cnt;
}
int f[N], fa[N];
int find(int x) {
while(x != f[x]) x = f[x] = f[f[x]];
return f[x];
//if(x!=f[x])f[x]=find(f[x]);
//return x;
}
void solve();
ll fast_mi(ll aa,ll bb){
ll res=1;
while(bb){
if(bb&1)res=res*aa%mod;
bb>>=1;
aa=aa*aa%mod;
}
return res;
}
int n;
struct oper {
int x, y;
} opt[N];
bool vis[N];
int dep[N];
vector <ll> ans;
ll son[N];
void bfs() {
queue <int> q;
vis[1] = true; q.push(1); dep[1] = 1; fa[1] = 1;
while(q.size()) {
int x = q.front(); q.pop();
for(int i = head[x]; i; i = nextt[i]) {
int y = to[i];
if(!vis[y]) {
dep[y] = dep[x] +1; fa[y] = x;
vis[y] = true; q.push(y);
}
}
}
}
int main(){
// freopen("data.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;T=1;
while(T--)solve();
return 0;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++) {
f[i] = i; son[i] = 1;
}
for(int i = 1; i < n; i++) {
cin >> opt[i].x >> opt[i].y;
}
for(int i = 1, x, y; i < n; i++) {
cin >> x >> y;
add(x, y); add(y, x);
}
bfs(); bool flag = true;
for(int i = 1; i < n; i++) {
int fx = find(opt[i].x), fy = find(opt[i].y);
if(dep[fx] < dep[fy]) { //depx > depy
swap(fx, fy);
}
// int fx = find(opt[i].x), fy = find(opt[i].y);
if(find(fa[fx]) == fy) {
ans.push_back(son[fx]); ans.push_back(son[fy]);
f[fx] = fy; son[fy] += son[fx];
} else {
flag = false; break;
}
}
if(!flag) {
cout << 0 << endl;
return ;
}
ll anss = 1;
for(int i = 0; i < ans.size(); i++) {
// cout << "i = " << i << " ansi = " << ans[i] << endl;
if(ans[i] != 1) anss = anss * fast_mi(ans[i], mod - 2) % mod;
}
cout << anss << endl;
return ;
}
J Minimum Manhattan Distance
分析：
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const double pi=acos(-1);
void solve();
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}
struct node{
double xx,yy;
};
double dis(node p1,node p2){
return sqrt((p1.xx-p2.xx)*(p1.xx-p2.xx)+(p1.yy-p2.yy)*(p1.yy-p2.yy));
}
void solve(){
node a,aa,bb,b,y1,y2;
double r1,r2,D,si,co;
cin>>a.xx>>a.yy>>aa.xx>>aa.yy>>b.xx>>b.yy>>bb.xx>>bb.yy;
y1.xx=(a.xx+aa.xx)/2;
y1.yy=(a.yy+aa.yy)/2;
y2.xx=(b.xx+bb.xx)/2;
y2.yy=(b.yy+bb.yy)/2;
D=dis(y1,y2);
r1=dis(a,aa)/2;
r2=dis(b,bb)/2;
si=abs(y1.yy-y2.yy)/D;
co=abs(y1.xx-y2.xx)/D;
printf("%.10lf\n",D*(si+co)-sqrt(double(2))*r2);
}
K Minimum Euclidean Distance
分析:
计算几何的代码不咋会写
标签：aa,int,ll,网络,ICPC,yy,fx,xx,2023 From： https://www.cnblogs.com/wzxbeliever/p/17719267.html