记次浙大月赛 134 - ZOJ Monthly, June 2014

虽做出的很少，也记录下来，留着以后来补。。浙大题目质量还是很高的

并查集的一些操作，同类和不同类我是根据到根节点距离的奇偶判断的，删点是直接新加一个点，记得福大月赛也做过类似的，并差集的这类关系题目还是比较常见的，有空深究一下。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 600010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int fa[N],res[N],mp[N];

 int dis[N];

 int find(int x)

 {

     if(fa[x]!=x)

     {

         int ro = find(fa[x]);

         dis[x]+=dis[fa[x]];

         return fa[x] = ro;

     }

     else

     return x;

 }

 int main()

 {

     int n,m,i;

     char s[];

     while(scanf("%d%d",&n,&m)!=EOF)

     {

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

         {

             fa[i] = i;

             res[i] = ;

             mp[i] = i;

             dis[i] = ;

         }

         int g = n+;

         while(m--)

         {

             int x,y;

             scanf("%s",s);

             if(s[]=='L')

             {

                 scanf("%d%d",&x,&y);

                 x = mp[x];

                 y = mp[y];

                 int tx = find(x);

                 int ty = find(y);

                 if(tx!=ty)

                 {

                     fa[tx] = ty;

                     dis[tx] = (dis[x]++dis[y]);//合并时应根据两树上的节点距离来确定两树的根节点距离

                     res[ty]+=res[tx];

                 }

             }

             else if(s[]=='Q')

             {

                 scanf("%d%d",&x,&y);

                 x = mp[x];

                 y = mp[y];

                 int tx = find(x);

                 int ty = find(y);

                 //cout<<tx<<" "<<ty<<endl;

                 if(tx!=ty)

                 {

                     printf("Unknown\n");

                     continue;

                 }

                 if((dis[x]-dis[y])%==)

                 printf("Same\n");

                 else

                 printf("Different\n");

             }

             else if(s[]=='S')

             {

                 scanf("%d",&x);

                 x = mp[x];

                 int tx = find(x);

                 printf("%d\n",res[tx]);

             }

             else

             {

                 scanf("%d",&x);

                 int xx = mp[x];

                 int tx = find(xx);

                 res[tx]-=;

                 mp[x] = ++g;

             }

         }

     }

     return ;

 }

离散化一下，枚举所有值所在的区间段，从左到右走一遍，采用边删边走的形式。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 map<int,int>f;

 vector<int>ed[N];

 vector<int>dd[N];

 int c[N];

 int main()

 {

     int n,k,i,j;

     while(scanf("%d%d",&n,&k)!=EOF)

     {

         f.clear();

         int g = ;

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

         {

             ed[i].clear();

             dd[i].clear();

         }

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

         {

             scanf("%d",&c[i]);

             if(!f[c[i]]) f[c[i]] = ++g;

             if(i==)

             {

                 dd[f[c[i]]].push_back(i);

                 continue;

             }

             int tg = f[c[i-]];

             if(c[i]!=c[i-])

             {

                 ed[tg].push_back(i-);

                 dd[f[c[i]]].push_back(i);

             }

         }

         ed[f[c[n]]].push_back(n);

         int ans = ;

         for(i = ; i <= g; i++)

         {

             int tk = ,st=,ss=;

             ss += ed[i][]-dd[i][]+;

             ans =  max(ans,ss);

             for(j =  ;j < ed[i].size() ; j++)

             {

                 tk+=(dd[i][j]-ed[i][j-]-);

                 ss+=(ed[i][j]-dd[i][j]+);

                 while(tk>k&&st<j)

                 {

                     tk-=(dd[i][st+]-ed[i][st]-);

                     ss-=(ed[i][st]-dd[i][st]+);

                     st++;

                 }

                 ans = max(ans,ss);

             }

         }

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

     }

     return ;

 }

这题有点逗，看了半个多小时终于看懂了啥意思，然后。。一份更逗的AC代码，全部输出1.

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100000

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int main()

 {

     int t,b,e;

     cin>>t;

     while(t--)

     {

         cin>>b>>e;

         cout<<"1\n";

     }

     return ;

 }

补坑

----------------------------------------------------------

dp,今天周赛鹏队把月赛题放出来了，上面3个都A过了，就去看这题。

这题着重点要放在有多少个不同的字母上面，用dp[i][g]表示有当前走了i步且有g个字母不同，往后递推步数，因为每次会变m个位置，那么可以枚举当前g个里面变了j个，那么len-g里面肯定要变m-j个。

那么久可以写出递推方程dp[i-g+m-g][j] = dp[i][j]*C(g,j)*C(len-g,m-j) 注意下边界问题。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 101

 #define LL long long

 #define INF 0xfffffff

 #define mod 1000000009

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 char s1[N],s2[N];

 LL dp[N][N],c[N][N];

 void init()

 {

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

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

             if(!j || i==j)

                 c[i][j]=;

             else

                 c[i][j]=(c[i-][j-]+c[i-][j])%mod;

 }

 int main()

 {

     int n,m,k,i,j,g;

     init();

     while(scanf("%d%d%d",&n,&k,&m)!=EOF)

     {

         memset(dp,,sizeof(dp));

         cin>>s1>>s2;

         if(strlen(s1)!=strlen(s2)||strlen(s1)<m)

         {

             puts("");

             continue;

         }

         int len = strlen(s1);

         int num = ;

         for(i = ;i < len ; i++)

         if(s1[i]!=s2[i])

         num++;

         dp[][num] = ;

         for(i = ; i <= k ; i++)

         {

             for(g = ; g <= len; g++)

             for(j =  ; j <= min(g,m) ;j++)

             {

                 if(len-g<m-j) continue;

                // cout<<i<<" "<<j<<endl;

                 dp[i][g-j+(m-j)]=(dp[i][g-j+(m-j)]+((dp[i-][g]*c[g][j])%mod*c[len-g][m-j])%mod)%mod;

 //                if(i==2&&j==0)

 //                {

 //                    cout<<c[num-g][m-j]<<" "<<num-g<<" "<<m-j<<endl;

 //                    cout<<i<<" "<<g-j+m-j<<" "<<dp[i][g-j+m-j]<<endl;

 //                }

             }

         }

         cout<<dp[k][]<<endl;

     }

     return ;

 }

tarjan缩点，然后找一个最长路，这个可以用topo思想来找最长的。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<stack>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 vector<int>ed[N];

 vector<int>dd[];

 vector<int>ee[N];

 int de[N],nn[N],dis[N];

 bool vis[N];

 int pre[N],lowlink[N],sccno[N],dfs_lock,scc_cnt;

 stack<int>S;

 void dfs(int u)

 {

     pre[u] = lowlink[u] = ++dfs_lock;

     S.push(u);

     for(int i =  ;i  < (int)ed[u].size() ; i++)

     {

         int v = ed[u][i];

         if(!pre[v])

         {

             dfs(v);

             lowlink[u] = min(lowlink[u],lowlink[v]);

         }

         else if(!sccno[v])

         lowlink[u] = min(lowlink[u],pre[v]);

     }

     if(lowlink[u]==pre[u])

     {

         scc_cnt++;

         int g = ;

         for(;;)

         {

             int x = S.top();S.pop();

             sccno[x] = scc_cnt;

             g++;

             if(x==u) break;

         }

         nn[scc_cnt] = g;

     }

 }

 void find_scc(int n)

 {

     dfs_lock = scc_cnt = ;

     memset(sccno,,sizeof(sccno));

     memset(pre,,sizeof(pre));

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

     if(!pre[i]) dfs(i);

 }

 int find()

 {

     int i;

     for(i =  ;i <= scc_cnt ; i++)

         dis[i] = ;

     queue<int>q;

     for(i =  ;i <= scc_cnt ; i++)

     {

         if(de[i]==)

         {

             q.push(i);

             dis[i] = nn[i];

         }

     }

     while(!q.empty())

     {

         int tu = q.front();

         q.pop();

         for(i = ; i < ee[tu].size() ; i++)

         {

             int v = ee[tu][i];

             dis[v] = max(dis[v],dis[tu]+nn[v]);

             de[v]--;

             if(de[v]==)

                 q.push(v);

         }

     }

     int ans = ;

     for(i =  ; i <= scc_cnt ; i++)

     ans = max(ans,dis[i]);

     return ans;

 }

 int main()

 {

     int i,m,n,j;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         memset(de,,sizeof(de));

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

         {

             ed[i].clear();

             ee[i].clear();

         }

         dd[].clear();

         dd[].clear();

         for(i = ; i <= m ;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);u--,v--;

             ed[u].push_back(v);

         }

         find_scc(n);

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

         {

             for(j = ;j < (int)ed[i].size() ; j++)

             {

                 int v = ed[i][j];

                 if(sccno[i]!=sccno[v])

                 {

                     vector<int>::iterator it;

                     int tu = sccno[i],tv = sccno[v];

 //                    it = lower_bound(ee[tu].begin(),ee[tu].end(),tv);

 //                    if(it==ee[tu].end()||(*it)!=tv)

 //                    {

                         ee[tu].push_back(tv);

                         de[tv]++;

 //                    }

                 }

             }

         }

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

     }

     return ;

 }

巴特西

记次浙大月赛 134 - ZOJ Monthly, June 2014

最新文章

热门文章