1 #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <sstream> 6 #include <string> 7 #include <algorithm> 8 #include <list> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <cstdlib> 15 // #include <conio.h> 16 using namespace std; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 #define inf 0x3f3f3f3f 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int N = 3*1e6+10; 22 const int MOD = 1e9+7; 23 #define LL long long 24 #define mi() (l+r)>>1 25 double const pi = acos(-1); 26 27 void fre() { 28 freopen("in.txt","r",stdin); 29 } 30 31 // inline int r() { 32 // int x=0,f=1;char ch=getchar(); 33 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 34 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 35 // } 36 int main(){ 37 int t,s,x; 38 cin>>t>>s>>x; 39 bool flag=false; 40 if(x<t) puts("NO"),exit(0); 41 if(((x-t)%s==0)||((x-t-1)%s==0&&x-t-1!=0)) flag=true; 42 if(flag) puts("YES"); 43 else puts("NO"); 44 return 0; 45 }
和上场有道差不多
1 // #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <sstream> 6 #include <string> 7 #include <algorithm> 8 #include <list> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <cstdlib> 15 // #include <conio.h> 16 using namespace std; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 #define inf 0x3f3f3f3f 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int N = 1e7+10; 22 const int MOD = 1e9+7; 23 #define LL long long 24 #define mi() (l+r)>>1 25 double const pi = acos(-1); 26 27 void fre() { 28 freopen("in.txt","r",stdin); 29 } 30 31 // inline int r() { 32 // int x=0,f=1;char ch=getchar(); 33 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 34 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 35 // } 36 37 int main(){ 38 string s; 39 int l=0; 40 cin>>s; 41 int pos=s.find('e'); 42 // cout<<pos<<endl; 43 for(int j=pos+1;j<=s.size()-1;j++){ 44 l=s[j]-'0'+l*10; 45 } 46 // cout<<l<<endl; 47 string str=""; 48 int pos2=s.find('.'); 49 // cout<<pos2<<endl; 50 for(int i=0;i<pos2;i++){ 51 str+=s[i]; 52 // cout<<str<<endl; 53 if(str[0]=='0'||l==0){ 54 str+='.'; 55 } 56 } 57 for(int i=pos2+1;i<pos;i++){ 58 str+=s[i]; 59 if(i-pos2==l) 60 str+='.'; 61 } 62 if(l>pos-pos2-1){ 63 for(int i=0;i<l-pos+pos2+1;i++){ 64 str+='0'; 65 } 66 } 67 if(str.find('.')!=-1){ 68 while(str.back()=='.'||str.back()=='0') str.pop_back(); 69 } 70 if(str=="") 71 str='0'; 72 if(l==0){ 73 cout<<str<<endl; 74 exit(0); 75 } 76 int p=0; 77 for(int i=0;i<(int)str.size();i++){ 78 if(str[i]!='0'&&str[i]!='.'){ 79 p=i; 80 break; 81 } 82 } 83 for(int i=p;i<(int)str.size();i++){ 84 cout<<str[i]; 85 } 86 cout<<endl; 87 return 0; 88 }
题意：完全二叉树 q次询问，op=1时，在x到y的最短边上c，op=2，输出x到y的权值和
思路：应为是完全二叉树，直接暴力每条边，加上权值，用mp存当前点到父亲的权值
1 // #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <sstream> 6 #include <string> 7 #include <algorithm> 8 #include <list> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <cstdlib> 15 // #include <conio.h> 16 using namespace std; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 #define inf 0x3f3f3f3f 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int N = 1e7+10; 22 const int MOD = 1e9+7; 23 #define LL long long 24 #define mi() (l+r)>>1 25 double const pi = acos(-1); 26 27 void fre() { 28 freopen("in.txt","r",stdin); 29 } 30 31 // inline int r() { 32 // int x=0,f=1;char ch=getchar(); 33 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 34 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 35 // } 36 map<LL,LL>mp; 37 void add(LL x,LL y,LL c){ 38 while(x!=y){ 39 if(x>y) swap(x,y); 40 mp[y]+=c; 41 y>>=1; 42 } 43 } 44 45 LL Sum(LL x,LL y){ 46 LL sum=0; 47 while(x!=y){ 48 if(x>y) swap(x,y); 49 sum+=mp[y]; 50 y>>=1; 51 } 52 return sum; 53 } 54 int main(){ 55 // fre(); 56 int T; 57 scanf("%d",&T); 58 mp.clear(); 59 while(T--){ 60 int op; 61 LL x,y,c; 62 scanf("%d",&op); 63 if(op==1){ 64 scanf("%I64d%I64d%I64d",&x,&y,&c); 65 add(x,y,c); 66 } 67 else{ 68 scanf("%I64d%I64d",&x,&y); 69 LL ans=Sum(x,y); 70 printf("%I64d ",ans); 71 } 72 } 73 return 0; 74 }
题意：n个节点，n-1个数，pi是i+1的父亲。问每个点的在随机DFS中访问次数的期望
题意：理解什么是随机dfs访问期望就简单了：非当前点的父亲节点和子孙节点的点，出现在该点的前后概率均为0.5；
所以dp[i]=dp[f]+1+0.5*(nodes[f]-nodes[i]-1);
f:i的父亲
nodes[]:i为根的树所含节点总数
所以，先处理每个点的子孙节点总数，再dp
对于当前点来说，父亲一定在dfs之前出现，所以次数+1,子孙不算，其余点要么在前要么在后，因此次数+0.5
1 // #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <sstream> 6 #include <string> 7 #include <algorithm> 8 #include <list> 9 #include <map> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <cstdlib> 15 // #include <conio.h> 16 using namespace std; 17 #define clc(a,b) memset(a,b,sizeof(a)) 18 #define inf 0x3f3f3f3f 19 #define lson l,mid,rt<<1 20 #define rson mid+1,r,rt<<1|1 21 const int N = 1e5+10; 22 const int MOD = 1e9+7; 23 #define LL long long 24 #define mi() (l+r)>>1 25 double const pi = acos(-1); 26 27 void fre() { 28 freopen("in.txt","r",stdin); 29 } 30 31 // inline int r() { 32 // int x=0,f=1;char ch=getchar(); 33 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} 34 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f; 35 // } 36 vector<int>g[N]; 37 int nodes[N]; 38 double dp[N]; 39 int pre[N]; 40 int dfs(int f){ 41 if(g[f].size()==0){ 42 return nodes[f]=1; 43 } 44 for(int i=0;i<g[f].size();i++){ 45 int v=g[f][i]; 46 dfs(v); 47 nodes[f]+=nodes[v]; 48 } 49 nodes[f]++; 50 } 51 52 double DP(int f){ 53 if(g[f].size()==0){ 54 return 0; 55 } 56 for(int i=0;i<g[f].size();i++){ 57 int v=g[f][i]; 58 dp[v]=dp[f]+1+0.5*(nodes[f]-nodes[v]-1); 59 DP(v); 60 } 61 } 62 int main(){ 63 fre(); 64 int n; 65 scanf("%d",&n); 66 pre[1]=-1; 67 for(int i=1;i<=n+1;i++) g[i].clear(); 68 for(int i=2;i<=n;i++){ 69 int x; 70 scanf("%d",&x); 71 if(x==i) continue; 72 g[x].push_back(i); 73 pre[i]=x; 74 } 75 dfs(1); 76 dp[1]=1.0; 77 DP(1); 78 for(int i=1;i<n;i++){ 79 printf("%.1lf ",dp[i]); 80 } 81 printf("%.1lf ",dp[n]); 82 return 0; 83 }