주윤달 NOIP 시뮬레이션 문제 주임비 문제풀이

T1 :

폭력 심수.설명 안 해.코드:

#include
#include
#include
#define f(x,y,z) for (int (x) = (y) ; x <= (z) ; x ++ )
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll size = 100;
ll ans = 0;
ll a[size],b[size],c[size],d[size];
ll n;

ll dfs(ll nn,ll oi,ll whk)
{
    if (nn == n+1)
    {
        if (ans < oi*whk) ans = oi * whk;
        return 0;
    }
    if (oi - b[nn] > 0 ) dfs(nn+1 , oi-b[nn] , whk+a[nn]);
    else dfs(nn+1, 0 ,whk+a[nn]);//    
    if (whk - d[nn] > 0 ) dfs(nn+1 , oi+c[nn] , whk-d[nn]); 
    else dfs(nn+1 , oi+c[nn]  ,0 );// oi 
}

int main(void)
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld",&n);
    for (ll i=1;i<=n;i++)
    scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);
    dfs (1,0,0);
    printf("%lld",ans); 
    return 0;
}

T2:

여기에 좋은 결론이 하나 있다. 나무 모양의 경로이기 때문에 한 구역 내의 연결 블록의 개수는 블록 안의 전체 검은 격자 수와 인접한 검은 블록의 대수를 빼는 것과 같다.처음에는 검은색 블록의 개수인 K개의 연결 블록이 있는데 한 쌍이 있으면 한 변을 연결하는 것과 같고 한 쌍이 있으면 하나의 연결 블록(나무 구조이기 때문)이 적기 때문에 연결 블록의 개수가 K-n쌍이라는 것을 증명할 수 있다.그리고 접두사와 통계, 통계변을 주의할 때 그 위나 왼쪽에 값을 주고 조회의 범위를 주의한다.사전 처리 복잡도 O(N2), 조회 복잡도 O(1).코드:

#include
#include
#include
#define f(x,y,z) for (int (x) = (y) ; x <= (z) ; x ++ )
using namespace std;
typedef int ll;
const ll MOD = 1000000007;
const ll size = 2010;
ll dop[size][size],l[size][size],up[size][size];
ll mat[size][size],tmp[size][size];
ll n,m,q;
char smat[size];

int main(void)
{
    scanf("%d%d%d",&n,&m,&q);
    for (ll i=1;i<=n;i++)
    {
        memset(smat,NULL,sizeof smat);
        scanf("%s",smat);   
        for (ll j=1;j<=m;j++)
        mat[i][j] = (int)(smat[j-1] - '0');
    }
    for (ll i=1;i<=n;i++)
    for (ll j=1;j<=m;j++)
    dop[i][j] = dop[i-1][j] + dop[i][j-1] - dop[i-1][j-1] + mat[i][j]; 

    for (ll i=1;i<=n;i++)
    for (ll j=1;j<=m;j++)
    {
        up[i][j] = up[i-1][j] + up[i][j-1] - up[i-1][j-1] ;
        if (mat[i+1][j]==1 && mat[i][j]==1) ++up[i][j];
    }

    for (ll i=1;i<=n;i++)
    for (ll j=1;j<=m;j++)
    if (mat[i][j] == 1 && mat[i][j+1]==1) l[i][j] = l[i-1][j] + l[i][j-1] -l[i-1][j-1] + 1; else
     l[i][j] = l[i-1][j] + l[i][j-1] - l[i-1][j-1]; 
    while (q--)
    {
        ll x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        ll all = dop[x2][y2] + dop[x1-1][y1-1] - dop[x1-1][y2] - dop[x2][y1-1];
        ll updot,ldot;
        updot = up[x2-1][y2] + up[x1-1][y1-1] - up[x1-1][y2] - up[x2-1][y1-1];
        ldot = l[x2][y2-1] + l[x1-1][y1-1] - l[x1-1][y2-1] - l[x2][y1-1];
        ll ans = all-updot-ldot;
        printf("%d
",ans);
    }
    return 0;
}

T3:

만약 한 점이 n줄의 선분에 의해 지나간다면, 그 귀축의 값은 n(n-4.1)/2이다.그래서 사실상 통계 역순이다. n개의 선이 지나가면 n(n-3-1)/2개의 역순이 있기 때문에 원래의 공식과 같다.그러나 이 문제는 공간이 넓기 때문에 우리는 하나하나의 유지보수, 즉 처음부터 끝까지 가장 가까운mod를 하나로 하고 그 다음은 다른 것으로 시작한다.계산할 때 줄 사이에만 역순이 있는 것을 계산한 다음에 공식을 밀어내면 끝난다.복잡도 O(N2 체인의 개수) = O(통과 가능).코드:

#include
#include
#include
#include
#define f(x,y,z) for (int (x) = (y) ; x <= (z) ; x ++ 
#define ni line[i].num
#define nj line[j].num
using namespace std;
typedef long long ll;
ll mod,n,begin,a,ans=0;
const ll MOD = 1000000007;
const ll size=100005;
struct WTF {
    ll str, num;
    inline ll operator * (const WTF &nima) {
         ll ste = (str -nima.str + a) / a;
         ll end = nima.num - ste + 1;
        if (end >= num) return num * ( 2 * ste + num-1)/2;
        return  end * (ste + nima.num )/2  + (ll)nima.num * (num - end);
    }
} line[size];ll cnt=0;
int main(void)
{
    scanf("%lld%lld%lld%lld",&n,&begin,&a,&mod);
    ll now = begin;ll y=0;
    while (y1 - now) /a + 1;
        if (y+num<=n)
        {
        line[cnt].num = num;
        (now += num*a)%=mod;
        y+=num;
        }
        else
        {
            line[cnt].num = n-y;
            y = n;
        }
    }
    for (ll i = 0;ifor (ll j = i+1 ; j<=cnt ; j++)
         ans+=line[i] * line [j];
    printf("%lld",ans);
    return 0;
}

4

결어:

이 문제의 대다수는 사고방식 문제이기 때문에 그래도 의의가 있다.