CF1245F Daniel and Spring Cleaning

題意：

給定l，r，求${\sum }_{a=l}^r{\sum }_{b=l}^r[a+b=a\oplus b]$

題解：

對(duì)于這個(gè)式子，只有當(dāng)a和b都不為0時(shí)成立，也就是我們不求
對(duì)于這個(gè)式子有f(x,y)=f(y,x)
考慮差分，f(r,r)-f(l-1,r)-f(r,l-1)+f(l-1,l-1)
答案為：f(r,r)-2f(l-1,r)+f(l-1,l-1)
數(shù)位dp轉(zhuǎn)移即可，數(shù)位dp還是dfs的轉(zhuǎn)移好寫(xiě)

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=50; ll dp[maxn][2][2][2]; int b[maxn],a[maxn]; ll dfs(int len,int flag1,int flag2,int flag3){if(!len){return flag3;}if(dp[len][flag1][flag2][flag3]!=-1)return dp[len][flag1][flag2][flag3];ll res=0;int up1=flag1?a[len]:1;int up2=flag2?b[len]:1;for(int i=0;i<=up1;i++){for(int j=0;j<=up2;j++){bool F=flag3;if((i&j)!=0)F=0;res+=dfs(len-1,(i==up1)&&flag1,(j==up2)&&flag2,F);}}return dp[len][flag1][flag2][flag3]=res; }ll solve(ll x,ll y){if(x<0||y<0)return 0;int num1=0,num2=0; memset(dp,-1,sizeof(dp));for(int i=0;i<=40;i++){a[i]=0;b[i]=0;}while(x){a[++num1]=x%2;x/=2;}while(y){b[++num2]=y%2;y/=2;}ll ans=dfs(32,1,1,1);return ans; } int main() {rd_test();int t;read(t);while(t--){ll l,r;read(l,r);cout<<solve(r,r)-2ll*solve(l-1,r)+solve(l-1,l-1)<<endl;}return 0;//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的CF1245F Daniel and Spring Cleaning(等会了更新)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。