背单词

背单词 【题目描述】 fqk 退役后开始补习文化课啦， 于是他打开了英语必修一开始背单 词。 看着满篇的单词非常头疼， 而每次按照相同的顺序背效果并不好， 于是 fqk 想了一种背单词的好方法！他把单词抄写到一个 n 行 m 列的 表格里，然后每天背一行或者背一列。他的复习计划一共有 k 天，在 k 天后， fqk 想知道，这个表格中的每个单词，最后一次背是在哪一 天呢？ 【输入格式】 第一行三个整数  n , m,k 。 接下来 k 行，每行的格式可能如下： 1. r ，表示当前天 fqk 背了第 r 行的单词。 2. c ，表示当前天 fqk 背了第 c 列的单词。 【输出格式】 输出包含 n 行， 每行 m 个整数， 表示每个格子中的单词最后一次背 是在哪天，如果这个单词没有背过，则输出 0 。 【输入样例】 3 3 3 1 2 2 3 1 3 【输出样例】 0 0 2 1 1 2 3 3 3 【数据范围】 对于 30% 的数据，n,m,k<=1000 。 对于 100% 的数据，n,m<=5000, n*m<=100000, k<=100000。 【时空限制】 对于每个测试点，时间限制为 s 1 ,空间限制为 MB 512 。

思路：

看到这个题，想到的第一个思路就是爆搜，但是看了数据范围之后，很显然，爆搜会超时的很厉害，为了解决超时的问题，我们不应该每读入一行或者一列，就把这行或这列的数全部赋值，而应该记录下每次更改的范围，在输出时使些小手段

#include<iostream> using namespace std; int h[5010],l[5010],p,n,m,k,q; int main() { freopen("word.in","r",stdin); freopen("word.out","w",stdout); cin>>n>>m>>q; int y; for(int i=1;i<=q;i++) { cin>>p>>y; if(p==1)h[y]=i; if(p==2)l[y]=i; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout<<max(h[i],l[j])<<" "; cout<<endl; } }