虽然去年做了挺多了也写了篇一句话题解了但一年过去也忘得差不多了$kk$
所以重新来整理下$kk$
$2018$
[X]积木大赛
大概讲下$O(n)$的数学方法.
我是从分治类比来的$QwQ$.考虑对每个点,如果它左侧比它高,显然可以在左侧被消的时候顺便把它消了.
否则只能消到左侧那个高度.
所以答案为$\sum max(0,a_i-a_{i-1})$
知识兔View Code#include<bits/stdc++.h> using namespace std; #define il inline #define gc getchar() #define ri register int #define rb register bool #define rc register char #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) int n,nw,pre,as; il int read() { ri x=0;rb y=1;rc ch=gc; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } int main() { //freopen("2611.in","r",stdin);freopen("2611.out","w",stdout); n=read();rp(i,1,n){nw=read();if(nw>pre)as+=nw-pre;pre=nw;}printf("%d\n",as); return 0; }[X]货币系统
一个结论:显然是从原来的集合中选出一个子集来.
我也不记得我怎么在考场上就突然想到这个结论了,,,感觉也挺显然的.所以也没啥严谨证明$QwQ$.
$luogu$题解里好像有个证明我有时间看下然后补上$QwQ$
反正知道这个结论之后就直接从小到大排序跑个背包就成$QwQ$.
知识兔View Code#include<bits/stdc++.h> using namespace std; #define ll long long #define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=50000,M=100+10; ll n,a[M],ans; bool f[N]; inline ll read() { char ch=getchar();ll x=0;bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')y=0,ch=getchar(); while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } inline void pre() { memset(f,0,sizeof(f));f[0]=1; } inline void work(ll x) { if(f[x]){--ans;return;} rp(i,0,a[n])if(f[i] && i+x<N)f[i+x]=1; } int main() { ll T=read(); while(T--) { pre(); n=read();rp(i,1,n)a[i]=read();sort(a+1,a+1+n);ans=n; rp(i,1,n)work(a[i]); printf("%lld\n",ans); } return 0; }[ ]赛道修建
,,,一年过去了$gql$还没落实$kk$
写下大概思路趴$QwQ$.
首先显然是二分.然后现在就是要$check$长度大于等于$mid$的道路数量是否大于等于$m$.
$dfs$遍就好.从小到大枚举能成道路就成道路,然后把剩下的最长的传上去,$over$
[ ]旅行
,,,一年过去了$gql$还没落实$kk$
发现只有树和基环树.
如果是树就很$easy$?每次跑到尽量小的就好$QwQ$.
然后基环树.
一个显然的想法是枚举断环上哪条边然后分别做树.
但是这样的做法的复杂度是$O(n^2)$,就不能通过加强版.所以港下$O(nlogn)$的做法$QwQ$
首先显然会被影响的只有在环上的操作,那就只看环了.
发现一个显然的结论是当.当前节点只有环上的儿子节点没有被访问,且当前节点祖先的未被访问最小儿子小于自己那个没有被访问的儿子节点时才会返回.
虽然句子很长但显然还是挺显然的$QwQ$.然后就做完了$QwQ$.
[ ]填数游戏
,,,咕咕
[ ]保卫王国
,,,咕咕.
$2017$
[X]小凯的疑惑
昂大概港下数学证明趴,,,?
考虑现在要构造最大的不能被表示出来的数.设这个数为$x$.
因为$(a,b)=1$,所以$x$一定能用$x=p\cdot a(mod\ b)(1\leq p\leq b-1)$表示出来.
于是设$x=p\cdot a+q\cdot b$.显然的是当$q>=0$时$x$就能用$a,b$表示出来了.所以$q_{max}=-1$.
然后因为$x$要尽量大,所以$x=p_{max}\cdot a+q_{max}\cdot b=(b-1)\cdot a+(-1)\cdot b=a\cdot b-a-b.$
$over$
(其实还有个很神的$exgcd$方法,,,是完完全全用$exgcd$做的没有猜结论啥的,,,但我没很$get$就没写了$kk$
知识兔View Code#include<bits/stdc++.h> using namespace std; long long a,b; int main() { cin>>a>>b; cout<<a*b-a-b; return 0; }[X]时间复杂度
大模拟不说,注意细节就成$QwQ$
知识兔View Code#include<bits/stdc++.h> using namespace std; long n,l,o2,ta,t2,ans,maxans,i; string s,ch,t; bool o1,o3; struct node{int b;char a;node(){b=0;}}str[101]; bool bj(string x,string y) { int lx=x.length();int ly=y.length();if(lx!=ly)return lx>ly; for(int i=0;i<lx;i++)if(x[i]!=y[i])return x[i]>y[i];return true; } int bs(string x){int lx=x.length();int ans=0;for(int i=4;i<lx-1;i++)ans=ans*10+x[i]-48;return ans;} int main() { cin>>n; while(n) { for(i=0;i<=100;i++)str[i].b=0;n--;ta=0;o1=0;o2=0;ans=0;maxans=0;cin>>l>>s; while(!l)cin>>s;if(s[2]=='1')t2=0;else t2=bs(s); for(i=1;i<=l;i++) if(!o1) { cin>>ch; if(ch=="E") { ta--; if(ta<0){cout<<"ERR"<<endl;o1=1;while(i<=l){getline(cin,ch);i++;}i=l+100;} if(str[ta+1].b==-1)o2++;if(str[ta+1].b==1)ans--;str[ta+1].b=0; } if(ch=="F") { cin>>ch; for(int j=1;j<=ta;j++) if(str[j].a==ch[0]){cout<<"ERR"<<endl;o1=1;while(i<=l){getline(cin,ch);i++;}} if(o1==0) { o3=0;ta++;str[ta].a=ch[0];cin>>ch; if(ch=="n"){cin>>ch;if(ch=="n")str[ta].b=0;if(ch!="n"){str[ta].b=-1;o2--;}o3=1;} if(o3==0) { t=ch;cin>>ch; if(ch=="n")if(o2>=0){ans++;str[ta].b=1;}if(ch!="n")if(bj(t,ch)){str[ta].b=-1;o2--;} } } } maxans=max(maxans,ans); } if(ta>0 && !o1)cout<<"ERR"<<endl,o1=1; if(!o1)if(maxans!=t2)cout<<"No"<<endl;else cout<<"Yes"<<endl; } return 0; }[X]逛公园
考虑先$dij$跑出最短路,然后设$f_{i,j}$表示当前决策到点$i$,浪费了$j$步的方案数,记搜就完事.
关于$0$环因为是记搜所以就每访问一个状态存到$stack$里面,如果本来就在$stack$里面了就说明有$0$环,最后出去的时候再从栈里丢出去就完事$QwQ$.
知识兔View Code#include<bits/stdc++.h> using namespace std; #define mp make_pair #define P pair<int,int> #define ri register int #define t1(i) edge1[i].to #define w1(i) edge1[i].wei #define t2(i) edge2[i].to #define w2(i) edge2[i].wei #define rp(i,x,y) for(ri i=x;i<=y;++i) #define e2(x) for(ri i=head2[x];i;i=edge2[i].nxt) const int N=100010,M=200010; int n,m,ret,mod,head1[N],head2[N],dis[N],tot,f[N][60],T; long long ans; struct ed{int to,nxt,wei;}edge1[M],edge2[M]; bool vis[N],instack[N][60],flg; priority_queue< P,vector<P>,greater<P> >Q; inline int read() { char ch=getchar();int x=0;bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(); while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } inline void pre() { tot=0;ans=0;flg=0; memset(instack,0,sizeof(instack));memset(f,0,sizeof(f)); memset(vis,0,sizeof(vis));memset(dis,0x333f,sizeof(dis)); memset(head1,0,sizeof(head1));memset(head2,0,sizeof(head2)); memset(edge1,0,sizeof(edge1));memset(edge2,0,sizeof(edge2)); } inline void add1(int x,int y,int z){edge1[++tot].to=y;edge1[tot].nxt=head1[x];edge1[tot].wei=z;head1[x]=tot;} inline void add2(int x,int y,int z){edge2[tot].to=y;edge2[tot].nxt=head2[x];edge2[tot].wei=z;head2[x]=tot;} inline void dij() { Q.push(mp(0,n));dis[n]=0; while(!Q.empty()) { ri t=Q.top().second;Q.pop(); if(vis[t])continue; vis[t]=1; e2(i)if(dis[t2(i)]>dis[t]+w2(i)){dis[t2(i)]=dis[t]+w2(i);Q.push(mp(dis[t]+w2(i),t2(i)));} } } int dfs(int u,int lf) { if(instack[u][lf])return flg=1,0;if(f[u][lf])return f[u][lf];instack[u][lf]=1;ri gdgs=0; for(ri i=head1[u];i!=0;i=edge1[i].nxt) { ri tmp=lf-dis[t1(i)]-w1(i)+dis[u]; if(tmp>=0 && tmp<=ret)gdgs=(gdgs+dfs(edge1[i].to,tmp))%mod; if(flg)return 0; } if(u==n && lf==0)gdgs=1;instack[u][lf]=0; return f[u][lf]=gdgs; } int main() { T=read(); while(T--) { pre();n=read();m=read();ret=read();mod=read(); rp(i,1,m){int t1=read(),t2=read(),t3=read();add1(t1,t2,t3);add2(t2,t1,t3);} dij();rp(i,0,ret){memset(instack,0,sizeof(instack));if(!flg)ans=(ans+dfs(1,i))%mod;} flg?printf("-1\n"):printf("%lld\n",ans); } return 0; }[X]奶酪
我是直接按高度排序,然后从所有能和上面/下面直接相连的洞$bfs$.
复杂度是$O(n^2),,,?$似乎是的$QwQ$.
知识兔View Code#include<bits/stdc++.h> using namespace std; #define ll long long #define rp(i,x,y) for(register ll i=x;i<=y;i++) struct nod { ll x,y,z; }node[1010]; ll n,h,r; bool flg,vis[1010]; ll read() { char ch=getchar();ll x=0;bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } bool cmp(nod a,nod b) { return a.z!=b.z?a.z>b.z:a.x>b.x; } inline void bfs(ll j) { if(node[j].z<=r)flg=0; if(!flg)return; ll i=j+1; while(i<=n && node[i].z+2*r>=node[j].z) { if(!vis[i]) if(4*r*r>=(node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y)+(node[i].z-node[j].z)*(node[i].z-node[j].z)) vis[i]=1; i++; } return; } int main() { ll t=read(); while(t--) { n=read(),h=read(),r=read();flg=1;memset(vis,0,sizeof(vis)); rp(i,1,n)node[i].x=read(),node[i].y=read(),node[i].z=read(); sort(node+1,node+1+n,cmp); rp(i,1,n) if(node[i].z+r>=h)vis[i]=1; else i=n+10; rp(i,1,n)if(vis[i])bfs(i); if(flg)printf("No\n"); else printf("Yes\n"); } return 0; }
[X]宝藏
$QwQ$我写了题解
我写的$dp$,设$f_{i,S}$表示当前决策到了第$i$层,点集状态为$S$的最小代价,转移下就完事$QwQ$.
复杂度不会算,,,$O($能过$)(bushi$
[X]列队
$QwQ$也写了题解
简单想法就给每一行及最后一列开一个$vector$,然后线段树维护第$i$个是$vector$上的第多少个.
然后就做完了$QwQQQQQQ$.
$2016$
[ ]玩具谜题
[ ]天天爱跑步
[ ]换教室
[ ]组合数问题
[ ]蚯蚓
[ ]愤怒的小鸟
$2015$
$2014$
$2013$
$2012$
$2011$
$2010$
$2009$
$2008$
$2007$
$2006$
$2005$
$2004$
$2003$
$2002$
$2001$
$2000$
$1999$
$1998$
$1997$