「CF718X」Codeforces Round #373 (Div. 1)
A. Efim and Strange Grade
给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入
问能最终能得到的最大的数
题解
考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入
如果四舍五入到小数点，将小数点去掉
最后再处理一下整数位的进位问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int 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; } int n,t,dot; char a[200005]; int main() { n=read();t=read();dot=n+1; scanf("%s",a+1); for(int i=1;i<=n;i++) if(a[i]=='.')dot=i; int p=-1; for(int i=dot+1;i<=n;i++) if(a[i]>='5'&&a[i]<='9') { p=i;break; } while(p>dot&&t>=1&&a[p]>='5'&&a[p]<='9') { a[p]=0; if(p-1!=dot)a[p-1]++; else a[p-2]++; t--;p--; } if(p==dot)a[p]=0,p--; while(a[p]=='9'+1) { if(p==1)putchar('1'); a[p]='0',a[p-1]++; p--; } printf("%s",a+1); return 0; } |
C. Sasha and Array
给定一个长度为n的数列an，有两种操作
1、将L到R的加上X
2、询问\(\sum_{L \leq i \leq R} F(a_i)\)
题解
考虑在线段树的每个结点维护一个斐波那契数列的转移矩阵
区间加法：就是将区间乘上v次的转移矩阵，标记下传同理
信息合并就是两个矩阵直接相加
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; int read() { int 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; } int n,m; int a[100005]; int ls[400005],rs[400005]; struct Mat{ int v[4]; Mat(){ memset(v,0,sizeof(v)); } friend Mat operator*(Mat a,Mat b){ Mat c; c.v[0]=(1LL*a.v[0]*b.v[0]+1LL*a.v[1]*b.v[2])%mod; c.v[1]=(1LL*a.v[0]*b.v[1]+1LL*a.v[1]*b.v[3])%mod; c.v[2]=(1LL*a.v[2]*b.v[0]+1LL*a.v[3]*b.v[2])%mod; c.v[3]=(1LL*a.v[2]*b.v[1]+1LL*a.v[3]*b.v[3])%mod; return c; } friend Mat operator+(Mat a,Mat b){ for(int i=0;i<4;i++)a.v[i]=(a.v[i]+b.v[i])%mod; return a; } friend Mat operator^(Mat a,int b){ Mat ans; ans.v[0]=ans.v[3]=1; for(int i=b;i;i>>=1,a=a*a) if(i&1)ans=ans*a; return ans; } }T,F,M[400005],tag[400005]; void build(int k,int l,int r) { int mid=(l+r)>>1; ls[k]=l;rs[k]=r;tag[k]=F; M[k].v[1]=1; if(l==r){M[k]=M[k]*(T^a[l]);return;} build(k<<1,l,mid); build(k<<1|1,mid+1,r); M[k]=M[k<<1]+M[k<<1|1]; } void pushdown(int k) { if(ls[k]==rs[k])return; tag[k<<1]=tag[k<<1]*tag[k]; tag[k<<1|1]=tag[k<<1|1]*tag[k]; M[k<<1]=M[k<<1]*tag[k]; M[k<<1|1]=M[k<<1|1]*tag[k]; tag[k]=F; } void add(int k,int x,int y,Mat v) { pushdown(k); int l=ls[k],r=rs[k],mid=(l+r)>>1; if(x==l&&y==r) { tag[k]=tag[k]*v;M[k]=M[k]*v; return; } if(x<=mid)add(k<<1,x,min(y,mid),v); if(y>mid)add(k<<1|1,max(x,mid+1),y,v); M[k]=M[k<<1]+M[k<<1|1]; } int query(int k,int x,int y) { pushdown(k); int l=ls[k],r=rs[k],mid=(l+r)>>1,ans=0; if(x==l&&y==r)return M[k].v[0]; if(x<=mid)ans+=query(k<<1,x,min(y,mid)); if(y>mid)ans+=query(k<<1|1,max(x,mid+1),y); return ans%mod; } int main() { T.v[1]=T.v[2]=T.v[3]=1; F.v[0]=F.v[3]=1; n=read(); m=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); for(int i=1;i<=m;i++) { int f=read(),l=read(),r=read(),x; if(f==1)x=read(); if(f==1)add(1,l,r,T^x); else cout<<query(1,l,r)<<endl; } return 0; } |
D. Andrew and Chemistry
给定一棵树，每个结点的度数小等于4
要在树上加一个结点，加完后度数依然小于4
问有多少不同构的加法
\(1\leq n\leq 10^5\)
题解
树的同构有经典的哈希做法，我们设法通过预处理，快速求得『在每个结点上加上一个结点后，新树的哈希值』
在树形递推的时候加上记忆化，mp(x,y)表示y的子树x的哈希值
由于树的度数很小，可以直接把每个结点x的儿子的哈希值一起放在vector里排好序，再把vector放到map里编x的哈希值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<map> #include<set> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int 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; } int n,cnt; int ans[100005]; vector<int>e[100005]; map<int,int> mp[100005]; map<vector<int>,int> H; set<int> st; int dp(int x,int fa) { if(mp[x][fa])return mp[x][fa]; vector<int> cur; for(int i=0;i<e[x].size();i++) if(e[x][i]!=fa) cur.push_back(dp(e[x][i],x)); sort(cur.begin(),cur.end()); if(!H[cur])H[cur]=++cnt; return mp[x][fa]=H[cur]; } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++) if(e[i].size()<4) st.insert(dp(i,0)); cout<<st.size()<<endl; return 0; } |
E. Matvey’s Birthday
求图的直径以及直径的数量
\(2\leq n\leq 10^5\)
题解
定义\(dis(i,c)\)为第i个位置到一个字符为c的位置的最短距离
定义\(d(c1,c2)\)为字符为c2的位置到字符为c2的位置的最短距离
以上枚举所有字母为起点广搜可得
(每个位置向「相邻位置」和「相邻位置」的字母连边，每个字母与「该字母的所有位置」连边）
我们发现两个位置的距离为
\(dis(i,j)=min(|i-j|,min\{dis(i,c)+1+dis(j,c)\})\)
注意到\(d(s_j,c)\leq dis(j,c)\leq d(s_j,c)+1\)，而\(d(c1,c2)\)通过预处理求得
\(dis(j,c)\)就可以由一个8位二进制数加上\(s_j\)复原
也就是说，当我们枚举 i 来计算\(dis(i,j)\)的时候，对于小于\(i-15\)的 j，就只需用\(c(s,st)\)记录字母为s，状态为st的 j 的数量
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define N 100005 using namespace std; int read() { int 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; } int n,ans; ll cnt; char a[N]; int dis[N][8],d[8][8],c[8][256],msk[N]; int q[N]; void bfs(int x) { int head=0,tail=0; for(int i=1;i<=n;i++) if(a[i]=='a'+x) dis[i][x]=0,q[tail++]=i; dis[x+n+1][x]=0; while(head!=tail) { int now=q[head];head++; if(now<=n) for(int i=-1;i<=1;i+=2) { int t=now+i; if(dis[t][x]>100&&1<=t&&t<=n) { dis[t][x]=dis[now][x]+1,q[tail++]=t; int c=a[t]-'a'+n+1; if(dis[c][x]>100) dis[c][x]=dis[now][x]+1,q[tail++]=c; } } else for(int i=1;i<=n;i++) if(a[i]=='a'+now-n-1&&dis[i][x]>100) dis[i][x]=dis[now][x]+1,q[tail++]=i; } } int main() { n=read(); scanf("%s",a+1); memset(dis,127/3,sizeof(dis)); for(int i=0;i<8;i++) { bfs(i); for(int j=0;j<8;j++)d[j][i]=dis[j+n+1][i]; } for(int i=1;i<=n;i++) for(int j=0;j<8;j++) msk[i]|=(dis[i][j]>d[a[i]-'a'][j])<<j; for(int i=1;i<=n;i++) { for(int j=max(i-15,1);j<i;j++) { int tmp=i-j; for(int k=0;k<8;k++) tmp=min(tmp,dis[j][k]+dis[i][k]+1); if(tmp>ans)ans=tmp,cnt=0; if(tmp==ans)cnt++; } int t=i-16; if(t>=1)c[a[t]-'a'][msk[t]]++; for(int j=0;j<8;j++) for(int k=0;k<256;k++) if(c[j][k]) { int tmp=100; for(int p=0;p<8;p++) tmp=min(tmp,d[j][p]+1+dis[i][p]+(k&(1<<p))); if(tmp>ans)ans=tmp,cnt=0; if(tmp==ans)cnt+=c[j][k]; } } cout<<ans<<' '<<cnt<<endl; return 0; } |
Subscribe
计数器 9850948
OI 课件=>
OI 课件=>