Educational Codeforces Round 115 (Div. 2)

A.思维
可以搜索
但是根据题目所给的移动条件，我们可以推断
只要从第一列到最后一列之间不存在同一列两行都为陷阱的情况
我们就一定可以到达
#include
using namespace std;
const int maxn = 110;
char g[110][3];
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		int n;cin>>n;
		for (int i=1;i<=n;++i)cin>>g[i][1];
		for (int i=1;i<=n;++i)cin>>g[i][2];
		string s = "YESn";
		for (int i=1;i<=n;++i)if (g[i][1]==g[i][2]&&g[i][1]=='1')
		{
			s = "NOn";
			break;
		}
		cout< 
B.暴力 
我们可以暴力枚举在第一、二两组在哪两天开会 

    
     
      
       
        d
       
       
        a
       
       
        
         y
        
        
         1
        
       
       
        ,
       
       
        d
       
       
        a
       
       
        
         y
        
        
         2
        
       
      
      
       day_1,day_2
      
     
    day1,day2 
然后，判断
    
     
      
       
        n
       
      
      
       n
      
     
    n个人能否均分为两组 
如果有人
     
      
       
        
         d
        
        
         a
        
        
         
          y
         
         
          1
         
        
        
         ,
        
        
         d
        
        
         a
        
        
         
          y
         
         
          2
         
        
       
       
        day_1,day_2
       
      
     day1,day2都没空，显然不可以
只在
     
      
       
        
         d
        
        
         a
        
        
         
          y
         
         
          1
         
        
       
       
        day_1
       
      
     day1有空的人和只在
     
      
       
        
         d
        
        
         a
        
        
         
          y
         
         
          2
         
        
       
       
        day_2
       
      
     day2有空的人不能超过
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        frac n2
       
      
     2n 
#include
using namespace std;
const int maxn = 1100;
int can[maxn][5];
int n;
void solve()
{
	for (int day1 = 0;day1<5;++day1)
		for (int day2 = day1+1;day2<5;++day2)
		{
			int cnt1 = 0,cnt2 = 0,cnt3 = 0;
			for (int i=1;i<=n;++i)
			{
				if (can[i][day1]&&can[i][day2])++cnt3;
				else if (can[i][day1])++cnt1;
				else if (can[i][day2])++cnt2;
			}
			if (cnt1+cnt2+cnt3!=n)continue;
			if (cnt1*2<=n&&cnt2*2<=n)
			{
				cout<<"YESn";
				return;
			}
		}
	cout<<"NOn";
}
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		cin>>n;
		for (int i=1;i<=n;++i)
			for (int j=0;j<5;++j)cin>>can[i][j];
		solve();
	}
}
 
C.模拟 
统计就好了 
如果我们已经知道了平均数
    
     
      
       
        a
       
       
        v
       
       
        e
       
      
      
       ave
      
     
    ave 
那么我们可以枚举所有的数
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai，根据平均数计算出
    
     
      
       
        
         a
        
        
         j
        
       
      
      
       a_j
      
     
    aj值,加上
    
     
      
       
        
         a
        
        
         j
        
       
      
      
       a_j
      
     
    aj出现的个数即可 
#include
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
int a[maxn];
int n;
map mp;
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		cin>>n;ll sum = 0;mp.clear();
		for (int i=1;i<=n;++i)cin>>a[i];
		for (int i=1;i<=n;++i)sum += a[i];
		if (sum*2LL%n!=0)
		{
			cout<<"0n";
			continue;
		}sum = sum*2LL/n;
		ll ans = 0;
		for (int i=1;i<=n;++i)
		{
			if (mp.count(sum-a[i]))ans+=mp[sum-a[i]];
			mp[a[i]]++;
		}cout< 
D.思维+计数 
数据量只支持
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)或者
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        g
       
       
        n
       
       
        )
       
      
      
       O(nlogn)
      
     
    O(nlogn)的解法 
我们观察题目所给的特殊的限制条件！ 
不存在一个点对
     
      
       
        
         (
        
        
         i
        
        
         ,
        
        
         j
        
        
         )
        
       
       
        (i,j)
       
      
     (i,j)使得
     
      
       
        
         
          a
         
         
          i
         
        
        
         =
        
        
         =
        
        
         
          a
         
         
          j
         
        
       
       
        a_i==a_j
       
      
     ai==aj且
     
      
       
        
         
          b
         
         
          i
         
        
        
         =
        
        
         =
        
        
         
          b
         
         
          j
         
        
       
       
        b_i==b_j
       
      
     bi==bj
满足条件的要求是
     
      
       
        
         
          a
         
         
          i
         
        
        
         ≠
        
        
         
          a
         
         
          j
         
        
        
         ≠
        
        
         
          a
         
         
          k
         
        
        
         ∣
        
        
         ∣
        
        
         
          b
         
         
          i
         
        
        
         ≠
        
        
         
          b
         
         
          j
         
        
        
         ≠
        
        
         
          b
         
         
          k
         
        
       
       
        a_inot=a_jnot=a_k||b_inot=b_jnot=b_k
       
      
     ai=aj=ak∣∣bi=bj=bk 
首先我们根据第一个条件，可以把所有点投射到一个
    
     
      
       
        2
       
       
        e
       
       
        5
       
       
        ∗
       
       
        2
       
       
        e
       
       
        5
       
      
      
       2e5*2e5
      
     
    2e5∗2e5的矩阵上 
行坐标为
    
     
      
       
        
         a
        
        
         i
        
       
      
      
       a_i
      
     
    ai，纵坐标为
    
     
      
       
        
         b
        
        
         i
        
       
      
      
       b_i
      
     
    bi 
因为条件一，所以每一个坐标点上最多只有一个点 
再根据条件二，思考一会发现直接求解是困难的 
考虑容斥 
什么情况下，不满足条件二呢？ 
选取的三个点中，至少有两个点在同一行，且至少有两个在同一列 
投射到矩阵上就是下面四种情况：
 
 
 
 
 我们计算每一行，每一列有多少个点，然后枚举每一个点作为中间节点，计算有多少种情况 
#include
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
int row[maxn],col[maxn];
int a[maxn],b[maxn];
int n;
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		cin>>n;
		for (int i=1;i<=n;++i)
		{
			cin>>a[i]>>b[i];
			row[a[i]]++;
			col[b[i]]++;
		}
		ll ans = 1LL*n*(n-1)*(n-2)/6LL;
		for (int i=1;i<=n;++i)
			ans -= 1LL*(row[a[i]]-1)*(col[b[i]]-1);
		cout< 
E.
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp+思维 
如果没有翻转的操作，单纯询问
    
     
      
       
        n
       
       
        ×
       
       
        m
       
      
      
       ntimes m
      
     
    n×m的矩阵中有多少个楼梯 
我们利用
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp计算 

    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        ,
       
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        :
       
      
      
       dp[0][i][j],dp[1][i][j]:
      
     
    dp[0][i][j],dp[1][i][j]:分别是以
    
     
      
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       (i,j)
      
     
    (i,j)为结尾的两种不同的楼梯个数 
并且我们把只取自身
    
     
      
       
        (
       
       
        i
       
       
        ,
       
       
        j
       
       
        )
       
      
      
       (i,j)
      
     
    (i,j)既看做成第一种也看做成第二种 

    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        =
       
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        +
       
       
        1
       
      
      
       dp[0][i][j]=dp[1][i-1][j]+1
      
     
    dp[0][i][j]=dp[1][i−1][j]+1 

    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        =
       
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        1
       
      
      
       dp[1][i][j]=dp[0][i][j-1]+1
      
     
    dp[1][i][j]=dp[0][i][j−1]+1 
最终统计以每一点为结尾的楼梯的个数 
即
    
     
      
       
        −
       
       
        n
       
       
        ×
       
       
        m
       
       
        +
       
       
        
         ∑
        
        
         
          (
         
         
          i
         
         
          ,
         
         
          j
         
         
          )
         
        
       
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        +
       
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       -ntimes m+sum_{(i,j)}dp[0][i][j]+dp[1][i][j]
      
     
    −n×m+∑(i,j)dp[0][i][j]+dp[1][i][j] 
利用
    
     
      
       
        c
       
       
        n
       
       
        t
       
      
      
       cnt
      
     
    cnt记录矩阵中
    
     
      
       
        f
       
       
        r
       
       
        e
       
       
        e
       
      
      
       free
      
     
    free状态的点，初始
    
     
      
       
        f
       
       
        r
       
       
        e
       
       
        e
       
       
        =
       
       
        n
       
       
        ×
       
       
        m
       
      
      
       free=ntimes m
      
     
    free=n×m 
当我们改动点
    
     
      
       
        (
       
       
        x
       
       
        ,
       
       
        y
       
       
        )
       
      
      
       (x,y)
      
     
    (x,y)时，
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        x
       
       
        ]
       
       
        [
       
       
        y
       
       
        ]
       
       
        ,
       
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        x
       
       
        ]
       
       
        [
       
       
        y
       
       
        ]
       
       
        ,
       
       
        c
       
       
        n
       
       
        t
       
      
      
       dp[1][x][y],dp[0][x][y],cnt
      
     
    dp[1][x][y],dp[0][x][y],cnt均发生改变 
当
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        x
       
       
        ]
       
       
        [
       
       
        y
       
       
        ]
       
      
      
       dp[0][x][y]
      
     
    dp[0][x][y]改变时，
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        +
       
       
        1
       
       
        ]
       
      
      
       dp[1][i][j+1]
      
     
    dp[1][i][j+1]也改变 
当
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        1
       
       
        ]
       
       
        [
       
       
        x
       
       
        ]
       
       
        [
       
       
        y
       
       
        ]
       
      
      
       dp[1][x][y]
      
     
    dp[1][x][y]改变时，
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        i
       
       
        +
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[0][i+1][j]
      
     
    dp[0][i+1][j]也改变 
如此，我们一路更新
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp的状态，会发现，至多更新
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n) 
因此，暴力更新
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp状态，维护
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp数组的和与
    
     
      
       
        c
       
       
        n
       
       
        t
       
      
      
       cnt
      
     
    cnt 
#include
using namespace std;
const int maxn = 1100;
typedef long long ll;
ll dp[2][maxn][maxn];
int g[maxn][maxn];
int n,m,q;
ll ans = 0;
void dfs(int x,int y,int sta)
{
	if (x>n||y>m)return;
	ans-=dp[sta][x][y];
	if (g[x][y]==1)dp[sta][x][y]=0;
	else if (sta==0)dp[sta][x][y] = dp[sta^1][x-1][y]+1;
	else dp[sta][x][y] = dp[sta^1][x][y-1]+1;
	ans+=dp[sta][x][y];
	if (sta==0)dfs(x,y+1,sta^1);
	else dfs(x+1,y,sta^1);
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m>>q;
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=m;++j)
		{
			dp[0][i][j]=dp[1][i-1][j]+1;
			dp[1][i][j]=dp[0][i][j-1]+1;
			ans+=dp[0][i][j]+dp[1][i][j];
		}
	}
	int cnt = n*m;
	while (q--)
	{
		int x,y;cin>>x>>y;
		if (g[x][y])++cnt;
		else --cnt;
		g[x][y]^=1;
		dfs(x,y,0);
		dfs(x,y,1);
		cout<
Educational Codeforces Round 115 (Div. 2)

C/C++/C#相关栏目本月热门文章
