周末DHU友谊赛(半日游)感想

DHU的校园挺好的啊，感觉教学楼啊，整体环境啊比咱学校好上一些，和大家一起出来有些春(冬)游的意味，食堂也是十分的宽敞，座位好多！

吐槽shu的食堂座位到饭点明显太少，食堂品类好多，shu的吃多了感觉没啥新奇的了呢。

然后友谊赛正题。昨天被徐州复现虐了，又打了广工的新生赛，打的还行叭，虽然没ak，真的挺想ak一次的(555估计没这机会了)，所以今天的友谊赛也有报一些期待。

最后只有4题滚粗。

我还是没自己想象中的强啊。

前期70多分钟，我交题一直没反馈，我以为大家都这样？也看不了榜(怎么可能交题不给反馈，我真的sb)然后就一直做下去，

做到第四题，看到了别人能看榜，我就tm立刻叫志愿者了，才知道我机子的域名不对，.120搞到.119去了，然后才开始交题，还是挺sb的吧我，下次比赛碰到异常情况一定要第一时间举手找帮助。

然后我看到第四题，榜1也才第四题，其实我做前面的题速度还不错的，然后就在77~80分钟将这三道题全交了，都是1A，还挺舒服。当然后来发现第二题没读题面，直接写dfs有点亏~

然后就随便模拟匹配了个D题，没自己测好，WA了3发，应该先自己找特殊情况测的，WA可以省，不要让judge给你罚时啊~

然后E就没了，我等等去补，dfs？拓扑？

然后后面2个小时差不多读了剩下的题，然后一直在想F，冲F(5发呀)

F就两个矩阵相乘，删去第一个矩阵的一行和第二个矩阵的一列使得答案最小，矩阵分别是n*m，和m*k的，都<=1000，

显然如果暴力矩阵乘法，nmk的复杂度承受不起，但题目里的矩阵考究的是以给非0元素的方式输入的，分别为p，q个，且数量都少于1000，少见必妖！所以以此为突破口；

我们记录第一个矩阵里的非0元素，输入第二个矩阵里的非0元素时，对p个第一矩阵中的元素遍历去生成我们的结果矩阵，复杂度可以降到p*q；细节见我的代码；

然后统计结果矩阵每行，每列的值，最后取 min(总的值-行-列+行列) 简单的容斥？反正就是把减了两遍的加上去即可。

（虽然这一步找最小值我想了好多假算法，比如删完行列的最大值，在统计列行的最大值，取更小，太假了，不具备一般情形。最后想到上面这个容斥，结论就显然正确了）

然后我的最终思路完全正确，但最后由于样例给的n=m=k，没测出来，我傻了，最后对sum[i][j] ，结果矩阵应该是n*k的，我用的都是 n和m ，md应该用n和k，真的sb，导致没冲过这题。我的青春结束了(滑稽）

细节上的处理呀，得自己造数据debug啊。

然后继续加油吧。贴个F代码。

 #include <bits/stdc++.h>

 #define debug(x) cout << #x << ": " << x << endl

 using namespace std;

 typedef long long ll;

 const int maxn=1e3+;

 const int INF=0x3f3f3f3f;

 const int MOD=1e9+;

 ll sum[maxn][maxn];

 ll sumr[maxn],sumc[maxn];

 struct node

 {

     ll x,y,v;

 }pp[maxn];

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     ll n,m,k;

     while(cin>>n>>m>>k)

     {

         memset(sum,,sizeof(sum));

         ll p,q,x,y,v;

         cin>>p>>q;

         for(ll i=;i<p;++i)

         {

             cin>>pp[i].x>>pp[i].y>>pp[i].v;

         }

         while(q--)

         {

             cin>>x>>y>>v;

             for(ll i=;i<p;++i)

             {

                 if(pp[i].y==x)

                 {

                     sum[pp[i].x][y]+=pp[i].v*v;

                 }

             }

         }

         ll ans=;

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

         {

             sumr[i]=;

             for(ll j=;j<=k;++j)

             {

                 sumr[i]+=sum[i][j];

                 //debug(sum[i][j]);

                 ans+=sum[i][j];

             }

             cout<<endl;

         }

         for(ll j=;j<=k;++j)

         {

             sumc[j]=;

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

             {

                 sumc[j]+=sum[i][j];

             }

         }

         ll res=ans;

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

         {

             for(ll j=;j<=k;++j)

             {

                 res=min(res,ans-sumr[i]-sumc[j]+sum[i][j]);

             }

         }

         cout<<res<<endl;

     }

     return ;

 }

巴特西

周末DHU友谊赛(半日游)感想

最新文章

热门文章