A.新年的巧克力棒
这道题我的做法是：如果有2^k个巧克力那么很好算，所以把给定的数字二进制拆分；
2得到1，4得到3，8得到7。。。每一个都是前一位的2倍+1
#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>using namespace std;int main(){int T;scanf("%d",&T);while (T–){int n;scanf("%d",&n);if (n<=1) puts("0");else{int ans=0,now=1;n>>=1;while (n){if (n&1) ans+=now;now=now*2+1;n>>=1;}printf("%d\n",ans);}}return 0;}
B.新年的毒瘤
很容易得到“毒瘤”的度数一定是m-(n-2)，而删去“毒瘤”还能构成一棵树，那么毒瘤一定不是割点。
因此毒瘤的充要条件就是：度数=m-(n-2)；不是割点
对于m=n-2的图要特殊处理一下，这种图中一定有一个点是孤立的，而这个点一定是毒瘤
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#define M 100005using namespace std;int is[M],tot,v[M],du[M],h[M],low[M],iscut[M],pre[M],dfs_clock=0;int n,m;struct Edge{int x,y;}E[M*2];struct edge{int y,ne;}e[M*3];bool ok=false;int cnt=0;void Addedge(int x,int y){e[++tot].y=y;e[tot].ne=h[x];h[x]=tot;}void tarjan(int u,int fa){low[u]=pre[u]=++dfs_clock;int child=0;for (int i=h[u];i;i=e[i].ne){int v=e[i].y;if (!pre[v]){child++;tarjan(v,u);low[u]=min(low[u],low[v]);if (low[v]>=pre[u])iscut[u]=1;}else if (pre[v]<pre[u]&&v!=fa)low[u]=min(low[u],pre[v]);}if (fa==0&&child==1) iscut[u]=0;}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);Addedge(x,y),Addedge(y,x);E[i].x=x,E[i].y=y;du[x]++,du[y]++;}if (m==n-1){int cnt=0;for (int i=1;i<=n;i++)if (du[i]==1) cnt++,is[i]=1;cout<<cnt<<endl;for (int i=1;i<=n;i++)if (is[i]) cout<<i<<" ";cout<<endl;return 0;}if (m==n-2){for (int i=1;i<=m;i++)is[E[i].x]=1,is[E[i].y]=1;cout<<1<<endl;for (int i=1;i<=n;i++)if (!is[i]) cout<<i<<endl;return 0;}tarjan(1,0);for (int i=1;i<=n;i++)if (!iscut[i]&&m-du[i]==n-2) cnt++,is[i]=1;cout<<cnt<<endl;for (int i=1;i<=n;i++)if (is[i]) cout<<i<<" ";cout<<endl;return 0;}C.新年的桌游
分类讨论。。
1.对于红太狼，有多少肯定就直接都出了
2.对于美羊羊，先判断能否通过她取得胜利，如果能，就直接出了；如果不能，她也并不是一无是处，可以作为对方出灰太狼的“威胁”，使得对方一直保持手里的灰太狼多于自己（让对方不敢出太多灰太狼）
3.接下来就是考虑灰太狼和喜羊羊了：计算双方获胜所需的最小局数，，取一个较小的就是胜者（注意要考虑美羊羊的威胁）
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#define inf 0x3f3f3f3fusing namespace std;int a[5],b[5];void D(){puts("Draw");}void X(){puts("Xiyangyang");}void M(){puts("Meiyangyang");}int main(){int T;scanf("%d",&T);while (T–){for (int i=1;i<=4;i++)cin>>a[i];for (int i=1;i<=4;i++)cin>>b[i];b[1]-=a[3],a[3]=0; //先手的红太狼if (b[1]<0){M();continue;}if (a[4]&&a[1]>=b[1]) //先手的美羊羊{M();continue;}if (a[1]&&!b[2]){M();continue;}a[1]-=b[3],b[3]=0; //后手的红太狼if (a[1]<0){X();continue;}if (b[4]&&b[1]>=a[1]) //后手的美羊羊{X();continue;}int x=inf,y=inf;if ((!b[4]&&a[1]>b[2])||(b[4]&&a[1]>b[1]+b[2]))x=b[2]+1;if ((!a[4]&&b[1]>a[2])||(a[4]&&b[1]>a[1]+a[2]))y=a[2]+1;if (x==inf&&y==inf) D();else if (x<=y){if (b[1]>=x-1&&x-1>a[2]) D();else M();}else{if (a[1]<=b[1]+1&&a[1]>=y-1&&y-1>b[2]) D();else if (a[1]>b[1]+1&&a[1]>=y&&y>b[2]) D();else X();}}return 0;}
D.新年的QAQ
我做了70分的点，先判断n是几，然后输出答案。判断n是几的方法是从0枚举到16看n与哪个相同。为了避免判断相同的误差，我的做法是：
如果判断相等，那么再次判断是否相等，如果还相等，再判断是否相等；如果不相等，从头开始判断。
如果判断不相等，那么再次判断是否不相等，如果还不相等，再判断是否不相等；如果相等，从头开始判断。
这样经过几轮（我进行了4轮）之后，如果每次判断都是一样的，那么这个判断基本可以保证是正确的。
下面是一个程序生成器。
我是在旅行吗？也许是的。
