AtCoder Beginner Contest 269「A」「B」「C 二进制枚举」「D 暴力dfs」「E 二分答案」「F 等差数列+推式子」
admin
|
|
304
|
Atcoder

1310 字
|
19 分钟

AtCoder Beginner Contest 269

A – Anyway Takahashi

题目描述：

输入a b c d，输出(a+b)*(c-d)，并输出Takahashi

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int a, b, c, d;

void work(){
    cin >> a >> b >> c >> d;
    cout << (a+b)*(c-d) << endl;
    puts("Takahashi");
}


int main(){
    io;
    work();
    return 0;
}

B – Rectangle Detection

题目描述：

给一个10*10的矩阵，矩阵只有两种元素，.和#,保证#形成一个矩形，输出矩形的左上角和右下角的坐标

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y, x2, y2;
char tr[15][15];

void work(){
    for(int i = 1; i <= 10; ++i){
        for(int j = 1; j <= 10; ++j){
            cin >> tr[i][j];
        }
    }
    bool p = 0;
    for(int i = 1; i <= 10; ++i){
        for(int j = 1; j <= 10; ++j){
            if(tr[i][j] == '#'){
                if(!p){
                    p = 1;
                    x = i;y = j;
                }
                x2 = i;y2 = j;
            }
        }
    }
    cout << x << ' ' << x2 << endl << y << ' ' << y2 << endl;
}


int main(){
    io;
    work();
    return 0;
}

C – Submask

题目描述：

给出一个十进制数字，把他拆成若干个不同的二的幂次方，作为一个集合，从小到大输出这个集合所有的子集合的数字的和

题目保证n的二进制数中1的数量不超过15

思路：

二进制枚举就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n;
vector<int>v;
void work(){
    cin >> n;
    bitset<64>b(n);
    for(int i = 0; i < 63; ++i){
        if(b[i] == 1)v.push_back(i);
    }
    for(int i = 0; i < (1ll << v.size()); ++i){
        bitset<30>fuck(i);
//        cout << fuck << endl;
        ll ans = 0;
        for(int j = 0; j < v.size(); ++j){
            if(fuck[j] == 1)ans += (1ll << v[j]);
        }
        cout << ans << endl;
    }
    cout << endl;
}


int main(){
    io;
    work();
    return 0;
}

D – Do use hexagon grid

题目描述：

网状图，六个方向相邻，问存在多少个联通块

思路：

暴力dfs即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
bool tr[2005][2005];
bool vis[2005][2005];

int dx[] = {-1, -1, 0, 0, 1, 1};
int dy[] = {-1, 0, -1, 1, 0, 1};

bool judge(int x, int y){
    if(x < 0 || y < 0 || x > 2000 || y > 2000)return false;
    if(vis[x][y] || !tr[x][y])return false;
    return true;
}

void dfs(int x, int y){
    vis[x][y] = 1;
    for(int i = 0; i < 6; ++i){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(judge(xx, yy))dfs(xx, yy);
    }
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x >> y;
        x += 1000;y += 1000;
        tr[x][y] = 1;
    }
    int ans = 0;
    for(int i = 0; i <= 2000; ++i){
        for(int j = 0; j <= 2000; ++j){
            if(!vis[i][j] && tr[i][j]){
                dfs(i, j);
                ++ans;
            }
        }
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

E – Last Rook

题目描述：

n*n的矩阵，同一行和同一列只存在一个皇后，即只有n个皇后，现在去掉一个皇后，你最多有20次询问机会，求出去掉的皇后的位置的在哪

每次询问可以输出? a b c d，代表询问以(a,c)为左上角，(b,d)为右下角的矩阵中的皇后的数量

思路：

观察数据范围，n<=1000，20次询问，2^10=1024>1000,所以考虑二分

对答案的x和y分开来二分答案即可

比如二分y的时候，我们写询问的左上角的x一直写1，右下角的x一直写n，这样就能保证查询的皇后的数量只与列的数量有关，问题就变成了：1到n中有n-1个1，1个0，在10次操作内找出0的位置。就是简单的二分

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, x, y, p;
int tr[MAX];

void work(){
    cin >> n;
    int l = 1, r = n;
    
    while(l <= r){
        int mid = (l + r) / 2;
        cout << "? " << 1 << ' ' << n << ' ' << l << ' ' << mid << endl;
        cin >> p;
        if(p == -1)exit(0);
        if(p == mid - l + 1)l = mid + 1;
        else r = mid - 1;
    }
    y = l;

    l = 1;r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        //cout << l << ' ' << r << ' ' << mid << endl;
        cout << "? " << l << ' ' << mid << ' ' << 1 << ' ' << n << endl;
        cin >> p;
        if(p == -1)exit(0);
        if(p == mid - l + 1)l = mid + 1;
        else r = mid - 1;
    }
    x = l;
    cout << "! " << x << ' ' << y << endl;
    
}


int main(){
    io;
    work();
    return 0;
}

F – Numbered Checker

题目描述：

给定一个n*m的矩阵，点(i, j)的值是(i-1)*m+j,现在把矩阵上所有i+j是奇数的点的值变成0

进行Q次询问，每次询问都查询一个子矩阵的数字和

思路：

利用类似于二位前缀和的操作，查询左上角(x1,y1)到右下角(x2,y2)的子矩阵的数字和，可以转换成计算左上角(1,1)到右下角(x,y)的矩阵去构造

所以怎么计算左上角(1,1)到右下角(x,y)的矩阵的数字和？

不难观察到，奇数行和偶数行的数的分布与计算并不一样，所以要分开讨论

拿题目给的图来说

81d92debe7aa949266f3a00cff13b513

先说奇数行，假设大矩阵是n行m列,我们可以发现奇数行的值是：

1 3

9 11

17 19

拆解一下得：

1 3

8+1 8+3

16+1 16+3

可以根据+拆成两部分看,一部分是每行都是1 3 5…这样开头，另一部分是每一行的每个数字从列上来看比上一行多一个2m，即公差为2m的等差数列

显然奇数行的数量是 , 奇数行中每一行的数的数量是

  • 第一部分： 1+3+5…是一个首项为1，公差为2的等差数列，显然数列长度是,则数列和是 ,一共有行，所以这一部分的答案是
  • 第二部分：第i行是一个长度为的常数数列，数列的值是2*(i-1)*m,由于各个行中的数字都相同，且行中的数字的数量也相同，是，所以我们只需要计算行与行之间每种数字的和，即首项为0，公差为2m，长度为的数列的和即可（即样例的0 + 8 + 16），所以第二部分的答案是：

偶数行也类似，自己推一下公式就行

这个题的感觉难点不在公式，在取模（bushi

取模换了好多种姿势才写过，服了都

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define y1 y114514
#define MAX 300000 + 50
ll n, m, k, x, y;
ll x1, x2, y1, y2;
int tr[MAX];

ll cal(ll x, ll y){
    ll a = (((((((y+1)/2)*m)%mod9) * ((x-1)/2)) %mod9 * ((x+1)/2)))%mod9;
    ll b = ((((x+1)/2) *((y+1)/2)) % mod9 * ((y+1)/2))%mod9;
    ll c = (((((y/2)*m)%mod9 * (x/2))%mod9 *(x/2))%mod9)%mod9;
    ll d = ((x/2) * (( ((y/2)*(y/2)) % mod9 + (y/2) )%mod9 ) % mod9)%mod9;
    return (((a + b)%mod9 + c)%mod9 + d)%mod9;
}

void work(){
    cin >> n >> m;
    cin >> k;
    while(k--){
        cin >> x1 >> x2 >> y1 >> y2;
        cout << ((((cal(x2, y2) - cal(x2, y1-1)+mod9)%mod9 - cal(x1-1, y2)+ mod9)%mod9 + cal(x1-1, y1-1))%mod9 + mod9)%mod9 << endl;
    }
}

int main(){
    io;
    work();
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
Atcoder
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
AtCoder Beginner Contest 266 「A」「B 取模」「C 凸多边形」「D 状态机dp」「E 概率dp」「F 思维+dfs」

							
							

							
ABC 216 G – 01Sequence「差分约束 」

							
							

							
AtCoder Beginner Contest 276「A」「B」「C」「D 思维」「E 联通块」「F 树状数组维护期望」

							
							

							
AtCoder Beginner Contest 239 E – Subtree K-th Max「树上“dp”」或「dfs序 && 主席树」

							
							

							
AtCoder Beginner Contest 233「D」「E」「F」