A.冰獄寒嵐

思路

我們將這個數對2048取模得k，如果k大于等于1024那么我們就返回k-2048否則直接返回k

Code

#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 ll ksm(ll a,ll b) {ll ans = 1;for(;b;b>>=1LL) {if(b & 1) ans = ans * a % mod;a = a * a % mod;}return ans; }ll lowbit(ll x){return -x & x;}const int N = 2e6+10;int a[N]; ll n,x;ll f(ll k) {k %= 2048;if(k >= 1024) return (k-2048);else return k; }int main() {cin>>n;for(int i = 1;i <= n; ++i) {cin>>a[i];a[i] = f(a[i]);}for(int i = 1;i <= n; ++i) {cout<<a[i]<<" ";}cout<<"\n";return 0; }

B.光之屏障

思路

我們用位運算模擬從小到大，或者從大到小模擬一下，看看是否有數落在這個范圍內，如果有輸出該數，否則輸出-1

Code

#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 ll ksm(ll a,ll b) {ll ans = 1;for(;b;b>>=1LL) {if(b & 1) ans = ans * a % mod;a = a * a % mod;}return ans; }ll lowbit(ll x){return -x & x;}const int N = 2e6+10;int a[N]; ll x,y;int main() {//ios::sync_with_stdio(false);int t;cin>>t;while(t--) {cin>>x>>y;bool fg = true;for(ll i = 0LL;i <= 32LL; ++i) {ll k = (1LL << i);if(k >= x && k <= y) {fg = false;cout<<k<<"\n";break;}}if(fg) puts("-1");}return 0; }

C.寒潭煙光

思路

很顯然算出$ans=\frac{n\times F(x)+n\times x_0+x_0}{n+1}$，注意這里爆int，所以我們直接輸出即可

Code

#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 ll ksm(ll a,ll b) {ll ans = 1;for(;b;b>>=1LL) {if(b & 1) ans = ans * a % mod;a = a * a % mod;}return ans; }ll lowbit(ll x){return -x & x;}const int N = 2e6+10;int a[N]; ll n,f,x;int main() {int t;cin>>t;while(t--) {cin>>n>>f>>x;cout<<(n * f + n * x + x)/(n + 1LL)<<endl;}return 0; }

D.金蛇狂舞

思路

因為實際上只有三種走法：

• 階乘
• 開根號然后向上取整
• 開根號然后向下取整

所以直接搜索然后注意下數據范圍剪枝即可:七步以上直接不搜，數據太大也不搜

Code

#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 ll ksm(ll a,ll b) {ll ans = 1;for(;b;b>>=1LL) {if(b & 1) ans = ans * a % mod;a = a * a % mod;}return ans; }ll lowbit(ll x){return -x & x;}const int N = 2e6+10; ll x,y; bool fg = false; int ans = 0x3f3f3f3f; ll f(ll k) {ll ans = 1;while(k) {ans *= k;k--;}return ans; } map<ll,bool>vis; void dfs(int cnt,ll loc) {if(cnt > 7 || loc > 10000000000LL ) {return;}if(loc == y) {fg = true;ans = min(ans,cnt);return;}if(loc <= 15)dfs(cnt+1,f(loc));//階乘dfs(cnt+1,ceil(sqrt(loc * 1.0) * 1.0));//向上取整dfs(cnt+1,sqrt(loc*1.0));//向下取整 }int main() {int t;cin>>x>>y;dfs(0,x);if(fg) cout<<ans<<endl;else puts("-1");return 0; }

E.暗滅侵蝕

思路

貪心的想，我們每次都跳動最左邊的球以最右邊的球為中心點，然后我們就能得到最優解，你可以這樣想，我們每次移動都是最優的，這其實有點像斐波那契數列

Code

#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 ll ksm(ll a,ll b) {ll ans = 1;for(;b;b>>=1LL) {if(b & 1) ans = ans * a % mod;a = a * a % mod;}return ans; }ll lowbit(ll x){return -x & x;}// const int N = 2e6+10; ll a,b,c,N;int main() {int t;cin>>t;while(t--) {cin>>a>>b>>c>>N;int cnt = 0;while(a < N && b < N && c < N) {ll ta = a;ll tb = b;ll tc = c;c = 2 * c - ta;a = tb;b = tc;cnt++;}cout<<cnt<<"\n";}return 0; }

F.火鳳燎原

思路

可能很多同學想到了將度大于等于3的點都跑一次DFS，但是只能過部分數據

很明顯有貢獻的點的度一定是大于等于三的：

• 此時這個 v 對于點 u 的貢獻，是以 v 為根的子樹大小減一（鏈的長度不少于 2，所以 v自己作為鏈的情況需要去除）。

我們稍加思索會發現一個結論，M為大于等于3的點的總數：$ans={\sum }_i^{M}n?d{u}_i?1$

證明后面補

Code

#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 ll ksm(ll a,ll b) {ll ans = 1;for(;b;b>>=1LL) {if(b & 1) ans = ans * a % mod;a = a * a % mod;}return ans; }ll lowbit(ll x){return -x & x;}const int N = 5e5+10;vector<int> Edge[N];int a[N]; ll n,x; int t;ll cnt; bool vis[N];void dfs(int loc,int deep) {if(vis[loc]) return;vis[loc] = true;if(deep >= 2) cnt++;for(int i = 0,len = Edge[loc].size();i < len; ++i) {dfs(Edge[loc][i],deep+1);} }int main() {scanf("%d",&t);while(t--) {scanf("%d",&n);for(int i = 1;i <= n; ++i) {Edge[i].clear();}int u,v;for(int i = 1;i < n; ++i) {scanf("%d%d",&u,&v);Edge[u].push_back(v);Edge[v].push_back(u);}ll ans = 0;for(int i = 1;i <= n; ++i) {if(Edge[i].size() >=3) ans +=n - Edge[i].size() - 1;}printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的牛客月赛42的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。