T1 方阵

题目

【题目描述】

小澳最近迷上了考古，他发现秦始皇的兵马俑布局十分有特点，热爱钻研的小澳打算在电脑上还原这个伟大的布局。

他努力钻研，发现秦始皇布置兵马俑是有一定规律的。兵马俑阵总共有n行m列，秦始皇在布置的时候每次会指定一行或一列，然后指定一个兵种，使得这一行或者这一列上全部放上这一个兵种。如果这一行上以前放过其它的兵种，那么他会拔掉以前的兵种改成现在他命令的兵种。

小澳从秦朝的文献中找到了布置这个方阵的操作顺序，他希望你能告诉他布局完成后整个兵马俑阵是什么样子的。

【输入格式】

输入文件共q+1行。  

输入文件第1行包括三个正整数n,m,q，分别表示兵马俑阵的行数和列数以及秦始皇总的操作数。

接下来q行，每行三个正整数x,y,z，x表示操作种类，若x=1表示给第y行(y≤n)全部放上z这个兵种，若x=2，则表示给第y列(y≤m)全部放上z这个兵种，数据保证z≤2³¹-1。

【输出格式】

n行，每行m个整数，分别用空格隔开。表示最后方阵上每个位置放的兵种，如果某个位置没有被操作过输出0。

【输入样例】

3 3 3
1 1 3
2 2 1
1 2 2

【输出样例】

3 1 3
2 2 2
0 1 0

【数据规模】

对于前20%的数据，n×m≤25。

对于前30%的数据，q≤2000。

对于100%的数据，n,m≤1000，n×m≤10⁵，q≤10⁶。

解析

惊！原题长乐培训Day4t1！

送分题，直接模拟即可，不过得从后往前来，不然会超时。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
struct rec{
    int p,x,y;
}s[1000010];
int n,m,q,map[1010][1010];
int main()
{
    //freopen("matrix.in","r",stdin);
    //freopen("matrix.out","w",stdout);
    int t;
    n=read(),m=read(),q=read();
    for(int i=1;i<=q;i++) s[i].p=read(),s[i].x=read(),s[i].y=read();
    for(int i=q;i>=1;i--)
    {
        if(s[i].p==1)
        {
            for(int j=1;j<=m;j++)
                if(!map[s[i].x][j]) map[s[i].x][j]=s[i].y;
        }
        else
        {
            for(int j=1;j<=n;j++)
                if(!map[j][s[i].x]) map[j][s[i].x]=s[i].y;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cout<<map[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

 

 

 

 

 

T2 排名

题目

【题目描述】

小明班里一共N名同学，小明这次考试考的不错，他知道他考了多少分，以及班级里的同学一共考了多少分，小明还知道这次考试满分为100，问小明最高可以排第几，最低可以排第几。

（相同分数算并列的排名，比如总共4个人7,6,6,5，那么他们的排名分别就是1,2,2,4）

【输入格式】

第一行包括三个整数N,A,S，分别表示班里同学的人数，小明的分数，以及班里同学的总分。

【输出格式】

包括两个用空格隔开的正整数，分别表示小明在最优情况下的排名，以及在最坏情况下的排名。

【输入样例】

5 90 450

【输出样例】

1 4

【数据规模】

对于40%的数据，1≤N≤10；

对于100%的数据，1≤N≤10⁵，0≤A≤100，0≤S≤100N。

解析

贪心：

计算最高排名时，先将所有人分数定为a，如果总分不够或总分刚好够，则第1；如果够，则逐渐增加满分人数，直到总分不够或刚好够，则排名为满分人数+1。

计算最低排名时，先将所有人分数定为a+1，如果总分不够，则排名为当前分数为a+1的总人数+1；如果够，则排名为n。

注意a=100分的情况(此时a+1=101，超出满分)，特判一下直接输出即可。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,a,s,num;
int high(int ans)
{
    for(int i=2;i<=n;i++)
    {
        if(ans>=a) ans-=a;
        else return 1;
    }
    if(ans==0) return 1;
    for(int i=2;i<=n;i++)
    {
        if(ans>=100-a) ans-=100-a;
        else return i;
        if(ans==0) return i;
    }
    return n;
}
int low(int ans)
{
    for(int i=1;i<n;i++)
    {
        if(ans>=a+1) ans-=a+1;
        else return i;
    } 
    return n;
}
int main()