第一题
题意:n个点,每个点坐标pi属性ai,从右往左将遇到的点向左ai范围内的点消除,后继续扫描。
现可以在扫描开始前提前消除从右往左任意点,问最少消除数(提前+扫描)。
n,pi,ai<=10^6
题解:很蠢的DP,我好蠢啊……
f[i]表示前i个的最少消除数(不含提前)
从左往右添加,每添加一个点x,它覆盖范围内的y个点失去作用,那么当前消除情况是f[x-y-1]+y,因为前面是不变的QAQ
简单的递推我都想半天……菜。
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f,maxn=1000010; struct cyc{int p,num;}a[maxn]; int n,b[maxn],sum[maxn]; bool cmp(cyc a,cyc b) {return a.p<b.p;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++)a[i].p=read(),a[i].num=read(),a[i].p++; sort(a+1,a+n+1,cmp); int cnt=1;sum[0]=0; for(int i=1;i<=maxn&&cnt<=n;i++) { sum[i]=sum[i-1]; if(a[cnt].p==i){sum[i]++;cnt++;} } int ans=n;b[0]=0; for(int i=1;i<=n;i++) { int now=a[i].p-a[i].num-1; if(now<0)now=0; b[i]=b[sum[now]]+sum[a[i].p]-sum[now]-1; ans=min(ans,b[i]+(n-i)); } printf("%d",ans); return 0; }
第二题
题意:给定a和b(两个正整数)加起来的结果和异或起来的结果,求a和b有几种搭配可能,ab不同时互换算两种。
a,b<=10^12
题解:x是和,y是异或答案
异或相当于每一位上进行不进位加法。
所以(x-y)>>1得到哪些位上做了进位,这些位上两个数都是1(y=0),只有一种可能。
一些位上y=0且不进位,这些位上两个数都是0,只有一种可能。
一些位上y=1,这些位上可以一数为0一数为1,有两种可能。
所以ans=2^(y中1的数量)。
但是还有一些不合法情况:
1.(x-y)的最低位不能是1,否则答案为0。
2.每一位上(x-y)>>1若是1则y必须也是0,否则答案为0。
3.x=y时答案-2,因为和与异或相等仅当不进位,不进位才可能出现0,此时不满足。
4.x<y时无解。
最后,记得1ll<<x!!!
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f; int n; ll x,y,ans=1; int main() { scanf("%lld%lld",&x,&y); ll num=x-y; if(num&1||x<y){printf("0");return 0;} num>>=1; for(int i=0;(1ll<<i)<=num;i++)if((num&(1ll<<i))&&(y&(1ll<<i))){printf("0");return 0;} for(int i=0;(1ll<<i)<=y;i++) { //printf("sfsdf"); if(y&(1ll<<i))ans=ans*2; //if((!y&(1<<i))&&(!num&(1<<i)))ans } if(x==y)ans-=2; printf("%lld",ans); return 0; }
第三题
题意:给定数字串,每次可以删去一个回文子串,删去后两端拼接,求最少次数删去全串。串长<=500。
题解:大力DP,O(n^3),好强啊……你们怎么都会DP。
虽然一眼区间DP感觉,但仔细一想就觉得很复杂啊……其实只要搞清楚转移方式,DP就会帮你完成复杂的工作。
区间DP最大的特点是按区间长度从小到大枚举,具有最优子结构!
考虑这道题的多个消除的回文之间只有两种可能:嵌套||并列,不可能交叉,这使区间DP成为可能。
f[i][j]表示删除i~j的最少次数,h[i][j]表示i~j是否回文,有以下情况:
1.回文:h[i][j]=1,即区间回文,f[i][j]=1。
2.嵌套:a[i]=a[j],尝试从a[i+1][j-1],已知a[i+1][j-1]最后删除的一步是回文,所以两端的i和j可以直接附加上,即f[i][j]=min(f[i][j],f[i+1][j-1]),步步推进。
3.并列:枚举将区间分成两部分,f[i][j]=min(f[i][j],f[i][x]+f[x+1][j])。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=510; int n,f[maxn][maxn],a[maxn]; bool h[maxn][maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++)f[i][i]=h[i][i]=h[i][i-1]=1; for(int p=2;p<=n;p++){ for(int i=1;i+p-1<=n;i++){ int j=i+p-1; h[i][j]=h[i+1][j-1]&(a[i]==a[j]); if(h[i][j])f[i][j]=1;else{ if(a[i]==a[j])f[i][j]=f[i+1][j-1]; for(int x=i;x<j;x++) f[i][j]=min(f[i][j],f[i][x]+f[x+1][j]); } } } printf("%d",f[1][n]); return 0; }