- (第一把 div1 心态崩了, 给大家表演了一把上蓝)
- (看来以后 div1 需要先读前三题, 如果没把握切掉还是不要交了......)
- A:
题意是求最少用几个形如 $2^{t}+p$ 的数拼出 n, 给定 n 和 p.$n\leq 10^{9},-1000\leq p\leq 1000,k\geq 0$.
我们不妨考虑如何判断一个 k 是否能成为答案. 显然移项之后变成了用 $2^{t}$ 拼某个数.
设 $n-kp$ 的二进制中有 a 个 1, 拼出它所用的 $2^{t}$ 个数为 num, 那么 $num_{min}=a$.
注意到我们可以把这 a 个中的某些 $2^{t}$ 拆成两个 $2^{t-1}$, 最多可以拆出 $n-kp$ 个(全用 1 拼).
感性理解一下, 显然 num 的可能取值是连续的. 那么只要判断 k 是否在 $[a,n+kp]$ 之间即可.
那我们应该枚举 k 到多少呢? 注意到 $a_{max}=log{n}$, 那么只要 k 枚举到 $log{n}$ 一定能找到解或者判断无解.
这么一个送分题我进入网页花了 5 分钟, 想了 5 分钟, 写了 5 分钟, 我真是活该掉分.
- #include<bits/stdc++.h>
- #define maxn 100005
- #define maxm 500005
- #define inf 0x7fffffff
- #define ll long long
- using namespace std;
- inline int read(){
- int x=0,f=1; char c=getchar();
- for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
- for(;isdigit(c);c=getchar()) x=x*10+c-'0';
- return x*f;
- }
- inline int calc(int x){int cnt=0;while(x){cnt+=(x&1);x>>=1;}return cnt;}
- int main(){
- int n=read(),p=read();
- if(n==p){printf("-1\n");return 0;}
- for(int i=1;i<=100;i++){
- n-=p; if(n<i){printf("%d\n",-1);return 0;}
- if(calc(n)<=i && i<=n){printf("%d\n",i);return 0;}
- }
- return 0;
- }
- A
- B:
题意是求有多少对 $i,j$ 满足 $a_{i}\cdot a_{j}=x^{k}$,$n\leq 10^{5},2\leq k\leq 100$.
看到这题大概是个人都有一个想法:
把 $a_{i}$ 质因数分解, 然后指数 $mod{k}$, 然后查找指数能和它匹配的个数.
然后我不知道怎么写这个东西好写, 于是去想了一些高论做法.
然而太菜什么都没想出来, 只好手写这个东西, 然后 re on 6.
我:???
你 wa on 6 我也可以调, 你 tm 的 re on 6 又不给 result, 我拿头调???
然后我陆续交了几发仍然 re, 于是心态崩了, 去打炉石.(一套海盗战从 10 砍到了 6, 强烈推荐)
比完之后我点开第一个 A 的 code, 发现他写了一个这样的东西.
map<vector<pair<int,int>>,int> ans;
我:???
积累一个实用小知识: 打 cf 一定要把 stl 的所有操作学好, 不然你 re 都不知道是怎么 re 的.
- #include<bits/stdc++.h>
- #define maxn 100005
- #define maxm 500005
- #define inf 0x7fffffff
- #define ll long long
- using namespace std;
- map<vector<pair<int,int>>,int> res;
- inline int read(){
- int x=0,f=1; char c=getchar();
- for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
- for(;isdigit(c);c=getchar()) x=x*10+c-'0';
- return x*f;
- }
- int main(){
- int n=read(),k=read(); ll ans=0;
- for(int nu=1;nu<=n;nu++){
- int x=read(); vector<pair<int,int>> a,b;
- //a.push_back(0),b.push_back(0);
- for(int j=2;j<=sqrt(x);j++){
- int p=0; while(x%j==0) x/=j,p++;
- p%=k; if(p==0) continue;
- a.push_back(make_pair(j,p));
- b.push_back(make_pair(j,k-p));
- }
- if(x!=1){
- a.push_back(make_pair(x,1));
- b.push_back(make_pair(x,k-1));
- }
- ans+=(ll)res[b],res[a]++;
- }
- cout<<ans<<endl;
- return 0;
- }
- B
- C:
由于上述原因 (海盗战 txdy) 我并没有看这道题. 今天上午胡了一下还胡错了, 我真是活该掉分.
题意大概是给你一个 $n\times m$ 的地图, 每个点要么是空的要么有石头.
你只能向下或向右走, 如果你撞到一个石头会把它推着一起走.
如果推到地图边界就不能再推了, 也就是不能再朝该方向走.
求有多少种方法从 $(1,1)$ 走到 $(n,m)$.$n,m\leq 2000$.
这种有限制的移动题一般还是考虑用 dp 去表示它的状态以及走法.
我们如果考虑从 $(1,1)$ 走到 $(i,j)$ 比较麻烦, 因为没法表示有多少石头的状态.
那如果倒着考虑, 从 $(i,j)$ 走到 $(n,m)$ 呢? 好多了, 可以通过石头个数判断后面能走哪. 但由于不知道走的方向比较麻烦.
考虑一条路径, 我们如果只在它转弯的地方进行 dp 转移, 就变得方便很多.
那么可以考虑设 $D_{i,j},R_{i,j}$. 其中 $D_{i,j}$ 表示现在在 $(i,j)$, 下一步要往下, 上一步不是往下的方案数.
设 $(i,j)$ 正下方有 k 个石头, 那么最多走 $n-k-i$ 步就必须右转了. 于是有 $D_{i,j}=\sum_{s=1}^{n-k-i}{R_{i+s,j}}$.
R 的转移类似. 我写了个 $O(nmlogn)$ 的, 其实记一下石头个数完全可以 $O(nm)$.
- #include<bits/stdc++.h>
- #define maxn 2005
- #define maxm 500005
- #define inf 0x7fffffff
- #define mod 1000000007
- #define ll long long
- using namespace std;
- char mp[maxn][maxn];
- ll n,m,d[maxn][maxn],r[maxn][maxn];
- ll cd[maxn][maxn],cr[maxn][maxn];
- ll nd[maxn][maxn],nr[maxn][maxn];
- inline ll read(){
- ll x=0,f=1; char c=getchar();
- for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
- for(;isdigit(c);c=getchar()) x=x*10+c-'0';
- return x*f;
- }
- inline ll mo(ll &x){return x>=mod?x-mod:x;}
- inline ll lowbit(ll x){return x&(-x);}
- inline ll sr(ll t,ll x){ll ans=0;for(ll i=x;i;i-=lowbit(i)) mo(ans+=cr[t][i]);return ans;}
- inline ll sd(ll t,ll x){ll ans=0;for(ll i=x;i;i-=lowbit(i)) mo(ans+=cd[t][i]);return ans;}
- inline ll qr(ll t,ll x,ll y){return (sr(t,y)-sr(t,x-1)+mod)%mod;}
- inline ll qd(ll t,ll x,ll y){return (sd(t,y)-sd(t,x-1)+mod)%mod;}
- inline void ar(ll t,ll x,ll y){for(ll i=x;i<=n;i+=lowbit(i)) mo(cr[t][i]+=y);}
- inline void ad(ll t,ll x,ll y){for(ll i=x;i<=m;i+=lowbit(i)) mo(cd[t][i]+=y);}
- int main(){
- n=read(),m=read();
- for(ll i=1;i<=n;i++) scanf("%s",mp[i]+1);
- for(ll i=1;i<=n;i++)
- for(ll j=m;j>=1;j--)
- nr[i][j]=nr[i][j+1]+(mp[i][j]=='R');
- for(ll i=n;i>=1;i--)
- for(ll j=1;j<=m;j++)
- nd[i][j]=nd[i+1][j]+(mp[i][j]=='R');
- d[n][m]=r[n][m]=1,ad(n,m,1),ar(m,n,1);
- for(ll i=n;i>=1;i--){
- for(ll j=m;j>=1;j--){
- if(i==n && j==m) continue;
- ll t1=nd[i+1][j],t2=nr[i][j+1];
- if(i+1<=n-t1) d[i][j]=qr(j,i+1,n-t1);
- if(j+1<=m-t2) r[i][j]=qd(i,j+1,m-t2);
- ad(i,j,d[i][j]),ar(j,i,r[i][j]);
- //cout<<i<<""<<j<<":"<<d[i][j]<<" "<<r[i][j]<<endl;
- }
- }
- if(n==m && n==1) cout<<(mp[1][1]=='.')<<endl;
- else cout<<(d[1][1]+r[1][1])%mod<<endl;
- return 0;
- }
- C
- D:
咕了, 补别的题(玩海盗战).
来源: http://www.bubuko.com/infodetail-3260440.html