题目已存档至百度网盘
前言: 还行,就是有人AK,令人不爽
方阵(matrix)
标程是记录每行每列的染色时间,我的做法是从指令最后往前处理,染色过的就不能再染了.时间复杂度为 O ( n + n m + q ) O(n+nm+q) O(n+nm+q),可以通过.
/*
从后往前排，排过的就锁住不能再排了
问题：1、快写居然出问题了
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXQ=1e6+5,MAXN=1e3+5;
int n,m,q,x[MAXQ],y[MAXQ],z[MAXQ],tot;
bool vish[MAXN],visl[MAXN],vis_map[MAXN][MAXN];
int ans[MAXN][MAXN];
inline int read()
{
int s=1,x=0;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')s=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
return s*x;
}
//void write(int x)
//{
// if(x<0)
// {
// x=-x;
// putchar('-');
// }
// else if(x>9)
// {
// write(x/10);
// }
// putchar();
//}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
n=read();
m=read();
q=read();
const int tot_map=n*m;
for(int i=1;i<=q;i++)
{
x[i]=read();y[i]=read();z[i]=read();
}
for(int i=q;i>=1;i--)
{
int h=y[i];
if(x[i]==1&&vish[h]==false)
{
for(int j=1;j<=m;j++)
{
if(vis_map[h][j]==false)
{
ans[h][j]=z[i];
vis_map[h][j]=true;
tot++;
}
}
vish[h]=true;
}
if(x[i]==2&&visl[h]==false)
{
for(int j=1;j<=n;j++)
{
if(vis_map[j][h]==false)
{
ans[j][h]=z[i];
vis_map[j][h]=true;
tot++;
}
}
visl[h]=true;
}
if(tot==tot_map)
break;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d",ans[i][j]);
putchar(' ');
}
putchar('
');
}
return 0;
}
另外,此题的write函数居然出锅了,应该这么写:
void write(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
else if(x>9)
{
write(x/10);
}
putchar(x%10+48);
}
即putchar(x%10+48)不是putchar(`x%10+48`)
坐标系(coordinate)
此题为Openjudge那道奶牛散步数据加强版,递推经典题呀.递推关系式为 f n = 2 f n − 1 + f n − 2 f_n=2f_{n-1}+f_{n-2} fn=2fn−1+fn−2.但今天做的时候显然忘记了,于是先搞了一个dfs把前几项算了出来.又因为前几天在接受数学的熏陶,弄了很久的差分表,结果发现根本弄不出来,直接吐血.(其实显然弄不出来,因为答案并不能被表示为多项式)
但好就好在,偶从差分表中看出了规律,最后列出了递推关系式.
另外,这道题数据范围过大,考虑优化.
方案一: 打表
在本机测试了用时:
1000000000
999999966
Use Time:16.217000
也就是说,我们将复杂度优化到 1 0 7 10^7 107即可.
我 们 已 经 知 道 了 f n = 2 f n − 1 + f n − 2 , 那 么 显 然 , 要 知 道 f n , 只 用 知 道 f n − 1 和 f n − 2 . 选 择 打 出 所 有 f n 与 f n + 1 ( n = 1 0 7 k , k 为 正 整 数 ) 我们已经知道了f_n=2f_{n-1}+f_{n-2},那么显然,要知道f_n,只用知道f_{n-1}和f_{n-2}.选择打出所有f_n与f_{n+1}(n=10^7k,k为正整数) 我们已经知道了fn=2fn−1+fn−2,那么显然,要知道fn,只用知道fn−1和fn−2.选择打出所有fn与fn+1(n=107k,k为正整数)
具体操作如下代码,也是考试时写出来的.打表的数据是用原本的未优化代码生成的.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll biao1[1005]={0,627935421,438953224,542068249,329814112,560895073,119554882,817838024,413683704,457693522,548686427,625090930,854797397,507897869,61876493,38377219,305397032,834552550,86754567,509991039,595114395,406847212,670491536,432878314,135680620,898309326,728242939,198112061,177816349,19047210,455754392,852650532,521176598,71125034,245305647,837039919,188113267,56598060,432474979,432717386,87865010,771920945,438742654,288408342,246724129,896686551,339943192,339062029,917394372,746339567,880572807,739796257,59753287,776287897,225152152,836502060,948930900,475746791,722277745,851272656,790561977,985377610,885700761,132420780,835281543,520522277,705708011,107967744,357214655,287632826,452485219,234406704,490642737,105936544,662318372,10700633,44184524,425184700,853280967,501062760,425337376,984713729,821083793,448257541,299730624,956477347,53544543,258784453,686484973,12946211,133711137,828167667,821810848,728440912,992782964,810060630,81297710,592494925,333385653,68086064,999999966};
ll biao2[1005]={0,316019740,372654023,224763656,22469312,782122008,34120220,931864090,425814224,323613731,426904732,655133268,419960676,600143856,636422754,404303050,514440356,364914981,228761950,38777592,133257557,122058434,66188449,284201981,606451036,708146069,58038914,491958600,718356299,472529774,855728576,454092882,3075198,128033925,672313652,274523182,685346016,965382417,79327031,70919624,314176084,524093558,507000754,423517629,401454042,306672104,839594331,294033500,29439574,960708835,59713600,296223267,981986607,148291544,877858011,326733601,500718454,694404815,412489057,164309652,746610433,220032885,261585106,940108177,802956593,46695727,852179533,782419693,57729179,975765453,190151629,400743276,947414172,856017108,746680441,337348962,303616399,286766519,671925310,423986587,856516568,213870031,317318877,493679984,182995823,98269674,305866735,16514990,809398153,525848172,231896493,533455685,956438514,294996456,409710864,32400151,771974784,207954764,741176549,835969528};
int main()
{
// freopen("coordinate.in","r",stdin);
// freopen("coordinate.out","w",stdout);
register long long f[3]={3,7};
register long long mod=1e9+7;
cin>>n;
if(n<=2)
{
cout<<f[n-1]<<endl;
return 0;
}
if(n<=10000000)
{
for(register int i=3;i<=n;i++)
{
f[2]=(2*f[1]+f[0])%mod;
f[0]=f[1],f[1]=f[2];
}
cout<<f[2]<<endl;
}
else
{
int k=n/10000000;
n%=10000000;
f[0]=biao1[k];
f[1]=biao2[k];
if(n<=1)
{
cout<<f[n]<<endl;
return 0;
}
for(register int i=2;i<=n;i++)
{
f[2]=(2*f[1]+f[0])%mod;
f[0]=f[1],f[1]=f[2];
}
cout<<f[2]<<endl;
}
return 0;
}
方案二: 矩阵快速幂
递推关系式的优化都可以用到矩阵快速幂,前几天讲课时也提到过,我已经写了一篇新的博客来介绍.