1007The Unsolvable Problem
水题不解释
#include<iostream> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<iomanip> #include<cstdio> using namespace std; int main() { int t; __int64 n; cin>>t; while(t--) { cin>>n; if(n==2) { cout<<1<<endl; continue; } if(n%2==1) { cout<<(n/2)*(n/2+1)<<endl; } else { if((n/2)%2==0) { cout<<(n/2-1)*(n/2+1)<<endl; } else { cout<<(n/2-2)*(n/2+2)<<endl; } } } return 0; }
1008 Pieces
这题我被坑了好久,最后还是按数位DP来写的,回头有能力的话再去写个更简单的。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <cassert> using namespace std; char s[20]; int dp[1<<16]; bool used[1<<16]; int l,q,shu; int main() { int t; scanf("%d",&t); getchar(); while(t--) { gets(s); l = strlen(s); for(int i=0;i<(1<<l);i++) { char ss[20]; shu = 0; for(int j=0;j<l;j++) { if(i >> j & 1) { ss[shu++] = s[j]; } } q = 1; for(int j=0,r=shu-1;j<shu;j++,r--) { if(ss[j] != ss[r]) { q = 0; break; } } used[i] = q; } dp[0] = 0; for(int i=1;i<(1<<l);i++) { dp[i] = 500000; for(int j=i;j>0;(--j) &= i) { if(used[j]) { dp[i] = min(dp[i],dp[i-j]+1); } } } printf("%d\n",dp[(1<<l)-1]); } return 0; }
1010 No Pain No Game
一开始思路不够开阔,竟然用N*2的算法去预处理,自然是各种TLE,回头用树状数组来处理,终于算是能用了,在经过各种优化之后时间终于突破1Kms。
#include<iostream> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<iomanip> #include<cstdio> using namespace std; int n,c[50005]; int a[50005],b[50005],ac[50005]; int lowbit(int x) { return x&(-x); } int add(int n) { int sum=0; while(n>0) { sum=max(sum,c[n]); n-=lowbit(n); } return sum; } void updata(int i,int x) { while(i<=n) { c[i]=max(c[i],x); i+=lowbit(i); } } struct node { int lw,hi,id; }s[50001]; bool cmp(node x,node y) { return x.lw>y.lw; } int main() { int i,t,m,j,k; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%d",&a[i]); } scanf("%d",&m); for(i=0;i<m;++i) { scanf("%d%d",&s[i].lw,&s[i].hi); s[i].id=i; } sort(s,s+m,cmp); i=n; j=0; memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); while(j<m) { for(;i>0&&i>=s[j].lw;--i) { for(k=1;k*k<=a[i];++k) { if(a[i]%k==0) { if(b[k]!=0) { updata(b[k],k); } b[k]=i; if(a[i]/k!=k) { if(b[a[i]/k]!=0) { updata(b[a[i]/k],a[i]/k); } b[a[i]/k]=i; } } } } while(j<m&&s[j].lw>i) { ac[s[j].id]=add(s[j].hi); j++; } } for(i=0;i<m;++i) { printf("%d\n",ac[i]); } } return 0; }
1011 Sad Love Story
写的时候想到了是最近点对,但是思路不够开阔,一直TLE,看了他人的写法才想到了优化方法,很抑郁。
当然最近点对的方法并不是最优化的方法,继续探究中。
1002Reincarnation
从来未写过的后缀自动机,直到现在还在研究中,代码等我研究明白再发、