Initiate

简单水题找规律

#include<iostream>
using namespace std;
int t,n,m,k;
int f(int a,int b)
{
 if(a==b){
  if(a%2==0) return 2*a;
  else return 2*a-1;}
 else if(a-2==b){
  if(a%2==0) return a+b;
  else return a+b-1;}
 else return -1;
 }
int main()
{
 cin>>t;
 while(t--)
 {
  cin>>m>>n;
  k=f(m,n);
  if(k==-1) cout<<"No Number"<<endl;
  else cout<<k<<endl;
  }
 return 0;
 }

递推。考虑最小的一个

f(m,n)=f(m,n-1)+f(m-n,n);

所有的方案=最少的一个盘子没有，m个全在其他N-1个中 + 最少盘子里至少有一个，即每个盘子里都至少有一个

#include<iostream>
using namespace std;
int t,n,m;
int f(int a,int b)
{
 if(a<0) return 0;
 if(a==0 || b==1 ||a==1) return 1;
 return f(a,b-1)+f(a-b,b);
 }
int main()
{
 cin>>t;
 while(t--)
 {
  cin>>m>>n;
  cout<<f(m,n)<<endl;
  }
 return 0;
 }

题目63位，刚好可以用long long 可以不用高精。由于规定了每一位的正负，一个数是可以唯一标示的。

而在一定的位数下，由奇偶性即可确定最后一位是1还是0，经过b-1次之后即可确定原来的数字。

#include<iostream>
#include<string>
using namespace std;
string s;
int res[100],k,m;
long long n;
int main()
{
int t,b;
cin>>t;
while(t--)
{
   k=0;
   cin>>b;
   m=b;
   cin>>s;
   cin>>n;
   while(1)
   {
   b--;
   if(b<0)
    {
    if(n==0){
    for(int i=m-1;i>=0;i--)
     cout<<res[i];
    cout<<endl;}
    else cout<<"Impossible"<<endl;
    break;
    }
   else{
   if(n%2==0)
    {res[k++]=0;
    n /= 2;
    }
   else{
    res[k++]=1;
    if(s[b]=='n')
    n=(n+1)/2;
    else if(s[b]=='p')
    n=(n-1)/2;
    }
    }
   }
}
return 0;
}

PS：LONGLONG不能递归？

题目:把一个带权值的树断开一条连线使其变为两个树，且这两部分的权值和之差最小。
算法:用向量组做邻接表存储数据，用dfs将树扫描一遍，从最底部开始判断。

#include<iostream>
#include<vector>
using namespace std;
int n,m,cas;
vector<int>vec[100010];
int per[100010],vis[100010];
long long cnt[100010];
long long total,res;
long long dfs(int t)
{
vis[t]=1;
cnt[t]=per[t];
for(int i=0 ;i<vec[t].size();i++)
{
   int a=vec[t][i];
   if(vis[a])continue;
   cnt[a] = dfs(a);
   cnt[t] +=cnt[a];
   long long temp;
   if(total-cnt[a]>=cnt[a])
    temp=total - 2*cnt[a];
   else
    temp=2*cnt[a]-total;
   if( temp < res ) res=temp;
   }
return cnt[t];
}
int main()
{
int i,j,p,q;
while (scanf("%d%d", &n, &m),n || m)
{
   total=0;
   res=1000000000000000LL;
   for(i=1;i<=n;i++)
   {
    scanf("%d", &per[i]);
    total +=per[i];
    vec[i].clear();
    cnt[i]=0;
    vis[i]=0;
   }
   for(i=1;i<=m;i++)
   {
    scanf("%d%d",&p,&q);
    vec[p].push_back(q);
    vec[q].push_back(p);
   }
   dfs(1);
   printf("Case %d: %lld\n", ++cas, res);
   }
return 0;
}