「CF698X」Codeforces Round #363 (Div. 1)
A. Vacations
题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天
用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息
简单dp一下
|
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 |
#include<map> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000007 #define inf 9000000000000000000LL using namespace std; ll read() { ll 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; int a[105],f[105][3]; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { if(a[i]>=2)f[i][2]=max(f[i-1][1],f[i-1][0])+1; if(a[i]==1||a[i]==3)f[i][1]=max(f[i-1][2],f[i-1][0])+1; f[i][0]=max(f[i-1][1],f[i-1][2]); f[i][0]=max(f[i-1][0],f[i][0]); } int ans=0; for(int i=0;i<=2;i++)ans=max(ans,f[n][i]); printf("%d\n",n-ans); return 0; } |
B. Fix a Tree
给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树
先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树
答案是环数-（是否存在自环）
|
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 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000007 #define inf 9000000000000000000LL using namespace std; ll read() { ll 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; } bool flag; int n,rt; int a[200005],d[200005]; bool vis[200005],mark[200005]; stack<int>st; void topsort() { while(!st.empty()) { int x=st.top();st.pop(); vis[x]=1; d[a[x]]--; if(!d[a[x]])st.push(a[x]); } } void dfs(int x) { vis[x]=1; if(!vis[a[x]])dfs(a[x]); } int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); if(a[i]==i) { flag=1; rt=i; } d[a[i]]++; } for(int i=1;i<=n;i++) if(!d[i])st.push(i); topsort(); int ans=0; for(int i=1;i<=n;i++) if(!vis[i]) { mark[i]=1; if(!rt)rt=i; ans++; dfs(i); } printf("%d\n",ans-flag); for(int i=1;i<=n;i++) if(mark[i])printf("%d ",rt); else printf("%d ",a[i]); return 0; } |
C.LRU
有n种物品，一个长度为K的缓存，每次以pi概率询问i物品是否在缓存中，不在则加入缓存，缓存物品超过K个丢弃最早加入的物品
问10^100次询问后，每个物品在缓存内的概率
用f(x)表示缓存里的物品状态数为x的概率，枚举一个不在缓存里的物品i，则
\[f(x|2^{i-1}) += f(x)*(p_i/ \sum_{i \in }p_i)\]
|
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 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 9000000000000000000LL using namespace std; ll read() { ll 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 K,n,bin[25]; lb f[1048576],p[25],ans[25]; lb dp(int x) { if(x==0)f[x]=1; int cnt=0; lb tot=0; for(int i=1;i<=n;i++) if((bin[i-1]&x)==0) tot+=p[i]; else cnt++; if(cnt>=K) { if(cnt>K)return 0; for(int i=1;i<=n;i++) if(x&bin[i-1])ans[i]+=f[x]; return f[x]; } for(int i=1;i<=n;i++) if((bin[i-1]&x)==0) { int t=(bin[i-1]|x); f[t]+=f[x]*(p[i]/tot); } return f[x]; } int main() { bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1; n=read();K=read();int m=n; for(int i=1;i<=n;i++) { cin>>p[i]; if(p[i]<=1e-10)m--; } K=min(K,m); for(int i=0;i<bin[n];i++)dp(i); for(int i=1;i<=n;i++) printf("%.16lf ",(double)ans[i]); return 0; } |
Subscribe
计数器 9302081
OI 课件=>
OI 课件=>