程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #221 (Div. 2) B. I.O.U. C. Divisible by S

Codeforces Round #221 (Div. 2) B. I.O.U. C. Divisible by S

編輯：C++入門知識

B. I.O.U.

題目鏈接：點擊打開鏈接

思路：

將每個人得多少、欠多少綜合起來看，一個關系內的debts最小就是得的總和或者欠的總和.

ps：這題數據貌似很水，很多代碼都水過了...

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#pragma comment (linker,/STACK:102400000,102400000)
#define maxn 1005
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,flag,cnt,best;
int in[maxn],out[maxn];

void solve()
{
    int i,j,t;
    ans=0;
    for(i=1;i<=n;i++)
    {
        ans+=max(0,in[i]-out[i]);
    }
}
int main()
{
    int i,j,t,pos,x,y,u,v,w;
    while(~scanf(%d%d,&n,&m))
    {
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        for(i=1;i<=m;i++)
        {
            scanf(%d%d%d,&u,&v,&w);
            out[u]+=w;
            in[v]+=w;
        }
        solve();
        printf(%d
,ans);
    }
    return 0;
}
/*
3 3
1 2 2
2 3 3
3 1 4
7 5
1 2 10
2 3 1
2 4 1
4 1 5
6 7 8
*/

C. Divisible by Seven

題目鏈接：點擊打開鏈接

思路：將1、6、8、9取出來，因為1689的排列所有除7的余數都能得到，所以可以將其他的數放在最前面，然後後面的缺幾就用1689的排列去補充就夠了。舉例：P為1689的排列，xxxP%7=((xxx0000%7)+(P%7))%7，求出xxx0000%7的余數為5的話，那麼構造一個P使得(P%7)余2就能夠使這個數被7整除了。

ps:當然，不能有前導0，所以還要分一個小情況。

感想：

比賽時想的就是這個構造方法，但是我SB的把1689的排列放在前面構造Pxxx的形式了，使處理變得復雜，而且這樣不能一定能構造到，所以就無盡的WA。。。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#pragma comment (linker,/STACK:102400000,102400000)
#define maxn 1005
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,flag;
bool vis[10];
string fac[7]=
{
    1869,1968,1689,
    6198,8691,8916,1896
};
string s,ss,anss,xx=0000;

int main()
{
    int i,j,t,pos,x,y,u,v,w;
    while(cin>>s)
    {
        memset(vis,0,sizeof(vis));
        ss=;
        for(i=0;i 
 


D. Maximum Submatrix 2題目鏈接：點擊打開鏈接
 
思路：
因為行可交換，列不能交換，所以每個數左邊右邊的數是不能變的。
先構造一個dp[i][j] 表示第i行第j個位置前面有多少個連續的1，這個很簡單，不用多說。
然後我們分析一下最優解的在未發生交換的形式，肯定是每一行都有幾個連續的1，然後拼起來就構成了一個最大的矩陣了。
那麼我們再構造一個cnt[col][j]，記錄一下第col列前面1的個數>=j的種行數，那麼最大值可以在dp[i][j]*cnt[j][dp[i][j]]中更新了。
 
代碼：
 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#pragma comment (linker,/STACK:102400000,102400000)
#define maxn 5005
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans;
char mp[maxn][maxn];
int dp[maxn][maxn],cnt[maxn][maxn];

void presolve()
{
    int i,j,t;
    memset(cnt,0,sizeof(cnt));
    for(i=1;i<=n;i++)
    {
        dp[i][0]=0;
        for(j=1;j<=m;j++)
        {
            if(mp[i][j]=='1') dp[i][j]=dp[i][j-1]+1;
            else dp[i][j]=0;
            cnt[j][dp[i][j]]++;
        }
    }
    for(int col=m;col>=1;col--)
    {
        for(j=m;j>=1;j--)
        {
            cnt[col][j]+=cnt[col][j+1];
        }
    }
}
void solve()
{
    int i,j,t;
    ans=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            t=dp[i][j]*cnt[j][dp[i][j]];
            ans=max(ans,t);
        }
    }
}
int main()
{
    int i,j,t;
    while(~scanf(%d%d,&n,&m))
    {
        for(i=1;i<=n;i++)
        {
            scanf(%s,mp[i]+1);
        }
        presolve();
        solve();
        printf(%d
,ans);
    }
    return 0;
}
/*
4 7
1001111
1110010
0111001
0110011
*/