期望得分：100+60+70=230

實際得分：0+60+0=60

?

T1

?

?

可以證明如果一對括號原本就匹配，那么這對括號在最優解中一定不會被分開

所以用棧記錄下沒有匹配的括號

最后棧中一定是 一堆右括號然后一堆左括號

ans=棧中右括號/2 上取整 + 棧中左括號 /2 上取整

?

#include<cstdio> #include<cstring>using namespace std;#define N 100001int top; char st[N];char s[N];int main() {freopen("shower.in","r",stdin);freopen("shower.out","w",stdout);scanf("%s",s+1);int len=strlen(s+1);for(int i=1;i<=len;i++)if(s[i]=='(') st[++top]='(';else if(top && st[top]=='(') top--;else st[++top]=')';int ans=0;int i;for(i=1;i<=top;i++)if(st[i]!=')') break;i--;printf("%d",(i+1)/2+(top-i+1)/2); } View Code

?

考試的時候 碰到右括號，沒有判斷此時棧頂是否是左括號

括號匹配只需要判斷 棧中是否有東西，因為一定是 左括號

這里因為有不合法的情況，所以需要判斷

?

?

T2

前綴和二分

#include<cstdio> #include<iostream>#define N 1000004using namespace std;bool vis[N]; int p[N],cnt;long long sum[N];void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void pre() {for(int i=2;i<N;i++) {if(!vis[i]) {p[++cnt]=i;sum[cnt]=sum[cnt-1]+p[cnt];}for(int j=1;j<=cnt;j++){if(i*p[j]>=N) break;vis[i*p[j]]=true;if(i%p[j]==0) break;}} }int main() {freopen("diary.in","r",stdin);freopen("diary.out","w",stdout);pre();int T,n,k;read(T);int l,r,mid,tmp;while(T--){read(n); read(k);l=k;r=lower_bound(p+1,p+cnt+1,n)-p;tmp=-1;while(l<=r){mid=l+r>>1;if(sum[mid]-sum[mid-k]<=n) tmp=mid,l=mid+1;else r=mid-1;}printf("%d\n",tmp==-1 ? -1 : sum[tmp]-sum[tmp-k]);} } View Code

?

60 暴力

#include<cstdio> #include<iostream> #include<algorithm>using namespace std;int T;#define N 1000004typedef long long LL;int p[N],cnt; bool vis[N];LL sum[N];struct node {int n,k,id; }e[2001];void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void pre() {for(int i=2;i<N;i++){if(!vis[i]) p[++cnt]=i;for(int j=1;j<=cnt;j++) {if(i*p[j]>=N) break;vis[i*p[j]]=true;if(i%p[j]==0) break;}}for(int i=1;i<=cnt;i++) sum[i]=sum[i-1]+p[i]; }namespace solve1 {void work(){int n,k,m; bool ok;for(int i=1;i<=T;i++){n=e[i].n; k=e[i].k;m=lower_bound(p+1,p+cnt,n)-p;ok=false;for(int i=m;i>=k && !ok ;i--)if(sum[i]-sum[i-k]<=n) { printf("%d\n",sum[i]-sum[i-k]); ok=true; }if(!ok) puts("-1");}} }namespace solve2 {int ans[2001];bool cmp(node p,node q){return p.k<q.k;}void work(){sort(e+1,e+T+1,cmp);int r=lower_bound(p+1,p+cnt+1,e[1].n)-p;int l=r;int now=1;while(now<=T){l=min(l,r-e[now].k+1);if(l<=0) break;while(l>1 && sum[r]-sum[l-1]>e[now].n) r--,l--;if(sum[r]-sum[l-1]>e[now].n) break;ans[e[now].id]=sum[r]-sum[l-1];now++;}for(;now<=T;now++) ans[e[now].id]=-1;for(int i=1;i<=T;i++) printf("%d\n",ans[i]);} }void init() {read(T); bool flag1=true,flag2=true;for(int i=1;i<=T;i++){read(e[i].n); read(e[i].k);if(e[i].n>100) flag1=false;if(e[i].n!=e[1].n) flag2=false;e[i].id=i;}if(flag1 || T==1) solve1::work();else if(flag2) solve2::work(); }int main() {freopen("diary.in","r",stdin);freopen("diary.out","w",stdout);pre();init(); } View Code

?

T3?

?

?

這算個DP套DP嗎

?

設g[i][j] 表示 在第i棵樹中，所有的點到j的權值和

F（t）=F（a）+F（b）+ size[a]*size[b]*l + g[a][c]*size[b] + g[b][d]*size[a]

size在合并的過程中 維護即可

?

求 g[i][j] ：

設dis[i][j][k] 在第i棵樹中，j到k的距離

?設現在要求g[t][k],有一條長為L的邊連接c和d

g[t][k]=g[A][k]+g[B][d]+(L+dis[A][k][c])*size[B]

?

求dis[i][j][k]：

如果本就是在一棵樹里，直接= dis[A][j][k]

否則

假設有一條長為L的邊連接了樹A中第點c和樹B中的點d,構成了第t棵樹

現在要求dis[t][p1][p2]

=dis[A][c][p1]+dis[B][d][p2]+L

?

g數組和dis數組不可能都存下來，每一次合并只涉及兩個點，記憶化搜索即可

?

注意：如果某點是在合并的第二棵樹里，編號還要減去第一棵樹的大小

?

?

#include<map> #include<cstdio> #include<iostream> #include<algorithm>using namespace std;typedef long long LL;const int mod=1e9+7;struct node {int p;LL p1,p2;node() {}node(int i,LL j,LL k){p=i;p1=min(j,k);p2=max(j,k);}bool operator < (node a) const{if(p!=a.p) return p<a.p;if(p1!=a.p1) return p1<a.p1;return p2<a.p2;} };map<pair<int,LL>,int>g; map<node,int>dis;int id1[61],id2[61],len[61]; LL num1[61],num2[61];LL siz[61];int f[61];void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void read(LL &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }int getDIS(int i,LL j,LL k) {if(!i) return 0;if(j==k) return 0;node x=node(i,j,k);if(dis.count(x)) return dis[x];if(j<siz[id1[i]]){if(k<siz[id1[i]]) return dis[x]=getDIS(id1[i],j,k);return dis[x]=(1LL*getDIS(id1[i],num1[i],j)+len[i]+getDIS(id2[i],num2[i],k-siz[id1[i]]))%mod; }else{if(k<siz[id1[i]]) return dis[x]=(1LL*getDIS(id1[i],num1[i],k)+len[i]+getDIS(id2[i],num2[i],j-siz[id1[i]]))%mod;return dis[x]=getDIS(id2[i],j-siz[id1[i]],k-siz[id1[i]]);} }int getG(int i,LL j) {if(!i) return 0;pair<int,LL>pr = make_pair(i,j);if(g.count(pr)) return g[pr];if(j<siz[id1[i]]) return g[pr]=((1LL*getDIS(id1[i],num1[i],j)+len[i])*(siz[id2[i]]%mod)%mod+getG(id2[i],num2[i])+getG(id1[i],j))%mod;return g[pr]=((1LL*getDIS(id2[i],num2[i],j-siz[id1[i]])+len[i])*(siz[id1[i]]%mod)%mod+getG(id1[i],num1[i])+getG(id2[i],j-siz[id1[i]]))%mod; }int main() {freopen("cloth.in","r",stdin);freopen("cloth.out","w",stdout);int m;read(m);siz[0]=1;for(int i=1;i<=m;i++){read(id1[i]); read(id2[i]); read(num1[i]); read(num2[i]); read(len[i]);f[i]=(f[id1[i]]+f[id2[i]]+(siz[id1[i]]%mod)*(siz[id2[i]]%mod)%mod*len[i]%mod+getG(id1[i],num1[i])*(siz[id2[i]]%mod)%mod+getG(id2[i],num2[i])*(siz[id1[i]]%mod)%mod)%mod;siz[i]=siz[id1[i]]+siz[id2[i]];cout<<f[i]<<'\n'; } } View Code

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/7751264.html

總結

以上是生活随笔為你收集整理的2017 清北济南考前刷题Day 2 afternoon的全部內容，希望文章能夠幫你解決所遇到的問題。

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