佳木斯集训Day8

本来能AK的啊啊啊啊啊，唯一一天可以AK，却被Champion误导了（好吧实际上是我理解有问题）

T1我写了俩小时，就是一道数列题，推公式的，可以二分解，我觉得二分麻烦，就直接想O（1）了

 #include <bits/stdc++.h>

 #define db double

 #define MAXN 5050

 #define ll long long

 int n;

 db a[MAXN],d[MAXN],sum,ans,gou;

 using namespace std;

 int main()

 {

     cin>>n;

     cin>>a[];

     cin>>sum;

     sum+=a[]*n;

     for(int i=;i<=n;i++)

     {

         cin>>d[i];

         sum-=*d[i]*(n+-i);

     }

     printf("%0.2f\n",sum/(n+));

     return ;

 }

T2简单啊...田忌赛马，直接一个DP完事儿了，不知道为什么好多人wa10，据说是贪心的锅，这道题贪心应该也可过，不过需要双指针

 #include <bits/stdc++.h>

 #define ll long long

 #define MAXN 1050

 using namespace std;

 int n,t,ans;

 int a[MAXN],b[MAXN],dp[MAXN][MAXN],f[MAXN][MAXN];

 bool cmp(int a,int b)

 {

     return a>b;

 }

 int main()

 {

     cin>>t;

     while(t--)

     {

         int maxn=;

         int minx=;

         int bigg=;

         int smalll=,ii,jj;

         cin>>n;

         for(int i=;i<=n;i++)

         {

             cin>>a[i];

             minx=min(minx,a[i]);

         }

         for(int i=;i<=n;i++)

         {

             cin>>b[i];

             maxn=max(maxn,b[i]);

         }

         /*if(minx>=maxn)

         {

             if(minx==maxn)

             cout<<(n-1)*200;

             else

             cout<<n*200;

             continue;

         }*/

         sort(a+,a++n,cmp);

         sort(b+,b++n,cmp);

         for(register int i=;i<=n;i++)

         {

             for(register int j=;j<=n;j++)

             {

                 if(a[i]>b[j])

                 dp[i][j]=;

                 else if(a[i]==b[j])

                 dp[i][j]=;

                 else

                 dp[i][j]=-;

             }

         }

     for (int i=;i<=n;i++)

     {

         f[i][]=f[i-][]+dp[n-i+][i];

         f[i][i]=f[i-][i-]+dp[i][i];

         for(int j=;j<i;++j)

         {

             f[i][j]=max(f[i-][j]+dp[n-i+j+][i],f[i-][j-]+dp[j][i]);

         }

     }

   //  for(int i=1;i<=n;i++)

    // cout<<f[i][1]<<" ";

     int sum=f[n][];

     for(int i=;i<=n;++i)

     sum=max(sum,f[n][i]);

     printf("%d\n",sum);

 }

     return ;

 }

T3裸的Tree DP，最后结果gcd一下就好了，啊啊啊啊啊我没有gcd结果wa0....

 #include <bits/stdc++.h>

 #define MAXN 1080

 using namespace std;

 bool vis[];

 int spfa[],dp[][];

 int n,m,k,nw,ny,ans,pos,l,r,num,top,maxn;

 int head[];

 queue <int>q;

 struct Node{

     int to,nxt,dis;

 }g[];

 void add(int u,int v,int dis)

 {

     g[++top].to=v;

     g[top].nxt=head[u];

     g[top].dis=dis;

     head[u]=top;

 }

 int work(int a)

 {

     return (a%+)%;

 }

 void dfs(int u,int fa)//父亲和当前的节点

 {

     dp[u][]=;

     for(int i=head[u];i;i=g[i].nxt)

     {

         int v=g[i].to;

         if(v==fa)

         continue;

         dfs(v,u);

         for(int j=;j<;j++)

         {

             ans+=dp[v][j]*dp[u][work(-j-g[i].dis)]*;

         }

         for(int j=;j<;j++)

         dp[u][work(j+g[i].dis)]+=dp[v][j];

     }

 }

 int main()

 {

     cin>>n;

     for(int i=;i<=n-;i++)

     {

         int x,y,z;

         cin>>x>>y>>z;

         add(x,y,z);

         add(y,x,z);

     }

     dfs(,-);

     ans+=n;

     maxn=n*n;

     int g=__gcd(ans,maxn);

    cout<<ans/g<<"/"<<maxn/g<<endl;

 }

巴特西

佳木斯集训Day8

最新文章

热门文章