暴力??

2024-09-02 18:38
文章标签 暴力

本文主要是介绍暴力??,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

又是苹果

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 54   Accepted Submission(s) : 12
Font: Times New Roman | Verdana | Georgia
Font Size:  

Problem Description

最近,亮亮和小W都对苹果很感兴趣!在研究了“最大苹果矩阵”和“给苹果树施肥”的问题后,他们又遇到了一个新的问题:

有一块长n米、宽m米的地,现在小W把地划分成边长1米的小正方形块,共n*m个块。每个块中可能种有一棵苹果树,或放有一个iPhone,也可以什么也没有。然而,亮亮拥有一种超能力,可以将2个宽1米、长度相同的矩形块在空间中直接交换。

亮亮经常对着农场施展超能力,为了不把自己搞晕,他每次总是选择两整行(长度均为m米)或两整列(长度均为n米)进行交换。小W对此十分恼火————当他想拿iPhone打游戏时,却莫名其妙地撞在了苹果树上。小W要求你写一个程序,帮助他确定某一正方形块中放了什么东西。

Input

输入包含多组数据,请处理到文件结束。
每组数据,第一行2个整数n、m,表示地的尺寸。
之后n行,每行m个英文字母,大写的T表示这里种有苹果树,小写的i表示这里放有iPhone,其他字符表示这里什么也没有。
之后1行,一个整数Q,表示小W询问的次数。
之后Q行,包含3个整数,可能有以下情况:
1 i1 j1 表示小W想知道第i1行第j1列的方块中有什么东西。
2 i1 i2 表示亮亮交换了第i1行与第i2行。
3 j1 j2 表示亮亮交换了第j1列与第j2列。
对于100%的数据,有1<=n*m<=10^6,1<=Q<=10^5,1<=i1,i2<=n,1<=j1,j2<=m。

Output

对于每组数据,输出以一行“Case #x:”开头,x表示数据的编号,从1开始。
对于小W的每次格式为“1 i j”的询问,输出一行。若方块中是苹果树,输出"Tree"。若方块中是iPhone,输出“Phone”。若方块中什么也没有,输出“Empty”。

Sample Input

2 2
Ti
Ti
2
1 1 1
1 2 2
3 3
Tct
Iai
qqT
3
1 1 3
2 1 2
1 1 3

Sample Output

Case #1:
Tree
Phone
Case #2:
Empty
Phone

Hint

输入数据只保证n*m在10^6以内,也就是说n和m都可能高达10^6。直接开10^6*10^6的数组肯定会MLE,请使用malloc或vector按需分配内存。

Author

xry111

直接模拟,两种交换操作的时间复杂度分别是O(n)、O(m),最坏情况下总时间复杂度为O(Q × max(n, m) + nm)显然会超时。注意到,如果连续进行一次行交换操作和一次列交换操作,无论这两次操作顺序如何,结果都不受影响。因此,对于行和列的交换操作,可分别定义表line和row,表示当前的第i行是原来的第line[i]行,第j列是原来的第row[j]列。这样,对于每次交换操作,只要交换两个数就行了,时间复杂度是O(1)。对于查询第i行j列的操作,直接返回原矩阵第line[i]行,row[j]列的元素就行了,时间复杂度O(1)。总的时间复杂度O(Q + nm)。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
int A[1000005];
char s[1000005];
int r[1000005],c[1000005];
char ans[3][20]={"Phone","Empty","Tree"};
int main()
{int n,m;int cas=1;while(~scanf("%d%d",&n,&m)){//memset(A,0,n*m*sizeof(int));int cnt=0;for(int i=1;i<=n;i++)r[i]=i;for(int j=1;j<=m;j++)c[j]=j;for(int i=1;i<=n;i++){r[i]=i;scanf("%s",s);int len=strlen(s);for(int j=0;j<len;j++){if(s[j]=='T')A[++cnt]=1;else if(s[j]=='i')A[++cnt]=-1;else A[++cnt]=0;}}int Q,a,b,op;cin>>Q;printf("Case #%d:\n",cas++);while(Q--){scanf("%d%d%d",&op,&a,&b);if(op==1){int x=A[(r[a]-1)*m+c[b]];puts(ans[x+1]);}else if(op==2){int t=r[a];r[a]=r[b];r[b]=t;}else{int t=c[a];c[a]=c[b];c[b]=t;}}}return 0;
}



这篇关于暴力??的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1130755

相关文章

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

10125-Sumsets【暴力】

利用n^2的时间枚举所有a[i] + a[j] 利用n^2的时间枚举所有a[i] - a[j] 之后利用n^2时间一个一个找a[i] - a[j]的值是否存在于a[i] + a[j]中 找的时候需要二分查找 另外一点就是注意long long的范围以及四个数是集合内不同的四个元素 15222638 10125 Sumsets Accepted C++ 0.449 2015-03-

10730-Antiarithmetic?【暴力枚举】

水题 求一个序列是否存在3个数按顺序构成等差数列 直接枚举等差数列的差值 时间复杂度降到 n * n / 3 开pos数组记录每个值得为之 楷vis数组记录目前i是否出现过 强行AC 15221397 10730 Antiarithmetic? Accepted C++ 0.035 2015-03-26 12:09:56 #include<cstdio>#include

HLJUOJ1125(暴力三点一线)

两点确定一条直线 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 19   Solved: 11 [ Submit][ Status][ Web Board] Description  给一个15000 * 15000 的区域, 坐标都是整数. 其中有N个点,N <= 770.问总共有多少个3点共线的组合.并按升序(点的ID)输出

HLJUOJ1117(暴力模拟)

八数码 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 109   Solved: 19 [ Submit][ Status][ Web Board] Description 给定一个8数码的初始状态,然后给出一系列对8数码的操作,求其最终状态. Input 第一行t,代表样例个数。 每组数据前三行各三个数,代表八数

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

UVA10010(八方向暴力枚举)

Where's Waldorf? Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu 题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18656 Description Where's Waldo

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There

CF#278 (Div. 2) A.(暴力枚举)

A. Giga Tower time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/A Giga To

CF#284 (Div. 2) B.(暴力)

题目链接:http://codeforces.com/contest/499/problem/B 解题思路: 开一个is变量记录每组单词最后应该输出哪个。最后每次把原来的数组暴力扫一遍即可。 完整代码: #include <functional>#include <algorithm>#include <iostream>#include <fstream>#inc