noip模拟测试10

时间：2021-08-12 09:38:56

T1：辣鸡

　　考试时一直在想怎样做到 nlog(n)

　　最开始想的是离散化后线段树加扫描线，然而空间爆炸……

　　最后写出n2暴力，然而并没有剪枝……

　　感觉写完模拟脑子就浆糊了

　　正解就是模拟，我也是醉了

　　

　　那说说怎么模拟（？？？）

　　先排个序，然后暴力选择2个矩形，看是否相邻，若相邻，则计算两矩形之间的贡献

　　再根据排序简单的进行可行性剪枝

　　就过了。就过了！

　　复杂度可以自己证明一下……

　　

　　so，code

　　

noip模拟测试10noip模拟测试10
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<queue>
 8 #include<cstdlib>
 9 #define ll long long
10 using namespace std;
11 const ll MAXN=100005;
12 int n;
13 ll ans;
14 struct node {
15     int ax,ay,bx,by;
16 }s[MAXN];
17 bool operator < (const node &aa,const node &bb) {
18     if(aa.ax!=bb.ax) return aa.ax<bb.ax;
19     return aa.ay<bb.ay;
20 }
21 void work() {
22     for(int i=1;i<=n;i++) ans+=(ll)(s[i].bx-s[i].ax)*(ll)(s[i].by-s[i].ay)*2ll;
23     
24     
25     for(int i=1;i<n;i++)
26         for(int j=i+1;j<=n;j++) {
27             if(s[i].bx+1<s[j].ax) break;
28             if(s[i].ax-1>s[j].bx) continue;
29             if(s[i].ay-1>s[j].by||s[i].by+1<s[j].ay) continue;
30             if((s[i].ax-1==s[j].bx||s[i].bx+1==s[j].ax)
31                 &&(s[i].ay-1==s[j].by||s[i].by+1==s[j].ay)) {
32                 ans++;
33             }else if(s[i].ax-1==s[j].bx||s[i].bx+1==s[j].ax) {
34                 int u=min(s[i].by,s[j].by),d=max(s[i].ay,s[j].ay);
35                 ans+=(ll)(u-d)*2ll;
36                 if(s[i].by>u||s[j].by>u) ans++;
37                 if(s[i].ay<d||s[j].ay<d) ans++;
38             } else if(s[i].ay-1==s[j].by||s[i].by+1==s[j].ay) {
39                 int l=max(s[i].ax,s[j].ax),r=min(s[i].bx,s[j].bx);
40                 ans+=(ll)(r-l)*2ll;
41                 if(s[i].ax<l||s[j].ax<l) ans++;
42                 if(s[i].bx>r||s[j].bx>r) ans++;
43             }
44         }
45     printf("%lld\n",ans);
46 }
47 int main() {
48     scanf("%d",&n);
49     for(int i=1;i<=n;i++) {
50         scanf("%d%d%d%d",&s[i].ax,&s[i].ay,&s[i].bx,&s[i].by);
51     }
52     sort(s+1,s+n+1);
53     work();
54     return 0;
55 }
t1 Code

 

T2：模板

　　这模板不清真……

　　考试时一点思路都没有，打个n2暴力走人

　　其实考试时就有一些思路了，想到了手写一颗splay，然后暴力启发式合并

　　但具体实现还是距正解较远

　　

　　说说正解吧

　　首先对于每一个节点，可以开一颗以操作时间为下标（或关键字）的线段树（或平衡树）

　　对于平衡树思路：大佬  sto TKJ orz 的博客

　　对于线段树思路 ：

　　　　线段树动态开点，对于每个节点，存两个信息——种类、数量

　　　　因为操作是针对u到根的链进行的，所以只需要在u节点上的线段树中修改下标为t的位置上修改

　　　　修改时，判断当前树中之前有没有出现过该颜色   （判断是否出现只需要记录一个某颜色的最早出现时间）

　　　　若出现过，则种类不加，只加数量 ; 否则都增加

　　　　最后从下至上统计，暴力将儿子的线段树和当前根的线段树启发式合并：

　　　　合并时暴力扫每一个有信息的节点，将信息暴力插入另一颗线段树即可

　　　　

　　　　但是！这里就有一个很大的问题！

　　　　合并时可能出现在当前颜色记录的出现最早时间之前插入该颜色（因为现在的插入并不是按照时间顺序的）

　　　　这时，我们就需要将之前记录的最早时间位置上对种类的贡献设为0

　　　　再将最早出现时间该为新的时间，并将新的时间上对种类的贡献设为1

　　　　（因为我们统计种类是根据第一次出现时间来统计）

　　　　

　　　　合并完后在线段树上查找小于桶的位置所包含的种类数就行了

　　　　

　　　　so，code

　　　　

noip模拟测试10noip模拟测试10
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<vector>
  7 using namespace std;
  8 const int MAXN=100005;
  9 int n,m,q,k[MAXN],ans[MAXN],clr[MAXN],book[MAXN],btot,pre[MAXN],used[MAXN],utot;
 10 vector<int> bl[MAXN];
 11 struct node {
 12     int to,nxt;
 13 }mp[MAXN*2];
 14 int h[MAXN],tot;
 15 void add(int x,int y) {
 16     mp[++tot].to=y;
 17     mp[tot].nxt=h[x];
 18     h[x]=tot;
 19 }
 20 int siz[MAXN],fa[MAXN],son[MAXN];
 21 void dfs1(int u) {
 22     siz[u]=bl[u].size()+1;
 23     for(int i=h[u];i;i=mp[i].nxt) {
 24         int v=mp[i].to;
 25         if(v==fa[u]) continue;
 26         fa[v]=u;
 27         dfs1(v);
 28         siz[u]+=siz[v];
 29         if(siz[v]>siz[son[u]]) son[u]=v;
 30     }
 31 }
 32 int root[MAXN];
 33 int ls[MAXN*20],rs[MAXN*20],val[MAXN*20],cnt[MAXN*20],ptot;
 34 int New() {
 35     return ++ptot;
 36 }
 37 void up(int p) {
 38     val[p]=val[ls[p]]+val[rs[p]];
 39     cnt[p]=cnt[ls[p]]+cnt[rs[p]];
 40 }
 41 void change(int &p,int l,int r,int x,int _val,int _cnt) {
 42     if(!p) p=New();
 43     if(l==r) {
 44         val[p]=_val,cnt[p]=_cnt;
 45         return;
 46     }
 47     int mid=(l+r)>>1;
 48     if(x<=mid) change(ls[p],l,mid,x,_val,_cnt);
 49     else change(rs[p],mid+1,r,x,_val,_cnt);
 50     up(p);
 51 }
 52 void insert(int u,int t,int c) {//在以 root[u] 为根的树中的 t 时刻插入 c 颜色
 53     if(!pre[c]) {
 54         used[++utot]=c;
 55         pre[c]=t;
 56         change(root[u],1,m,t,1,1);
 57     }
 58     else if(pre[c]<t)
 59         change(root[u],1,m,t,0,1);
 60     else if(pre[c]>t) {
 61         change(root[u],1,m,pre[c],0,1);
 62         change(root[u],1,m,t,1,1);
 63         pre[c]=t;
 64     }
 65 }
 66 void merge(int p,int l,int r,int &rt) {
 67     if(!p) return;
 68     if(l==r) {
 69         if(cnt[p]) insert(rt,l,clr[l]);
 70         return;
 71     }
 72     int mid=(l+r)>>1;
 73     merge(ls[p],l,mid,rt);
 74     merge(rs[p],mid+1,r,rt);
 75 }
 76 int query(int p,int l,int r,int lim) {
 77     if(!p||!lim) return 0;
 78     if(l==r) return val[p];
 79     int mid=(l+r)>>1,ret=0;
 80     if(ls[p]&&lim<cnt[ls[p]])
 81         ret+=query(ls[p],l,mid,lim);
 82     else {
 83         ret+=val[ls[p]];
 84         ret+=query(rs[p],mid+1,r,lim-cnt[ls[p]]);
 85     }
 86     return ret;
 87 }
 88 void clear() {//清空颜色标记
 89     while(utot) pre[used[utot--]]=0;
 90 }
 91 void solve(int u) {
 92     for(int i=h[u];i;i=mp[i].nxt) {
 93         int v=mp[i].to;
 94         if(v==fa[u]||v==son[u]) continue;
 95         solve(v); clear();
 96     }
 97     if(son[u]) solve(son[u]);
 98     root[u]=root[son[u]];
 99     for(int i=0;i<bl[u].size();i++)
100         insert(u,bl[u][i],clr[bl[u][i]]);
101     for(int i=h[u];i;i=mp[i].nxt) {
102         int v=mp[i].to;
103         if(v==fa[u]||v==son[u]) continue;
104         merge(root[v],1,m,u);
105     }
106     
107     ans[u]=query(root[u],1,m,k[u]);
108 }
109 
110 int main() {
111     scanf("%d",&n);
112     for(int i=1,aa,bb;i<n;i++) {
113         scanf("%d%d",&aa,&bb);
114         add(aa,bb),add(bb,aa);
115     }
116     dfs1(1);
117     for(int i=1;i<=n;i++) scanf("%d",&k[i]);
118     scanf("%d",&m);
119     for(int i=1,aa,bb;i<=m;i++) {
120         scanf("%d%d",&aa,&bb);
121         clr[i]=bb;book[i]=bb;
122         bl[aa].push_back(i);
123     }
124     sort(book+1,book+m+1);
125     btot=unique(book+1,book+m+1)-book-1;
126     for(int i=1;i<=m;i++) clr[i]=lower_bound(book+1,book+btot+1,clr[i])-book;
127     solve(1);
128     scanf("%d",&q);
129     for(int i=1,aa;i<=q;i++) {
130         scanf("%d",&aa);
131         printf("%d\n",ans[aa]);
132     }
133     return 0;
134 }
t2 Code

 

T3：大佬

　　这道题的思路真的是强啊

　　开始我一直在想如何解决对于作业难度序列上1到k天的难度选择对于2到k+1天的影响

　　最后考完才知道，可以直接统计全局答案

　　

　　怎么理解呢？

　　当k=3时

　　假设我们对于1到k天选择一种难度序列：1 3 1

　　那么我们是不是在计算2到k+1天的答案时就只能用最大值为3的情况来计算了呢？

　　不是的，因为我们上述列出的只是所有情况中的一种

　　而如果我们抽出个例对于全局来看，2到k+1天的答案不一定只能用3来计算

　　那么我们就可以用全局的公式来计算总期望了：

　　　　　　$(n - k + 1) \sum \limits _{i = 1} ^ m\{[ i^k - (i - 1) ^k ] m^{-k} w_i\}$

 　　意义：共（n - k + 1）天

　　　　　 每天有$i^k - (i - 1) ^k$种情况使 i 成为最大值

　　　　　 即：用1到i填k个空的方案减去其中没有i的方案，没有i的方案等价与用1到 i - 1填的方案

　　　　　 总共有$m^k$种情况，概率为$[ i^k - (i - 1) ^k ] m^{-k}$

　　

　　so，code

　　

noip模拟测试10noip模拟测试10
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define ll long long
 7 using namespace std;
 8 const int MAXN=505,D=1000000007;
 9 ll w[MAXN],ans,n,m,k;
10 ll qpow(ll x,ll k) {
11     ll ret=1;
12     while(k) {
13         if(k&1) ret=(ret*x)%D;
14         x=(x*x)%D;
15         k>>=1;
16     }
17     return ret%D;
18 }
19 int main() {
20     scanf("%lld%lld%lld",&n,&m,&k);
21     if(k>n) return !printf("0\n");
22     for(int i=1;i<=m;i++) scanf("%lld",&w[i]);
23     for(int i=1;i<=m;i++)
24         ans=(ans+(qpow(i,k)-qpow(i-1,k))*w[i]%D)%D;
25     ans=(ans*qpow(qpow(m,D-2),k)%D*(n-k+1))%D;
26     printf("%lld\n",(ans+D)%D);
27     return 0;
28 }
t3 Code

 

　　

　　

 

标签：

相关文章