洛谷官方题单【算法1】
|
86
|
0
|
🎓 理工

【1-1】模拟与高精度

[NOIP2003 普及组] 乒乓球

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

const int N = 62500 + 5;
char str[N];
int cnt = 0;
void show(int n){

    int a = 0, b = 0;
    for(int i = 0; i < cnt; ++ i){
        if(str[i] == 'W') a ++;
        if(str[i] == 'L') b ++;

        if((a >= n || b >= n) && abs(a - b) >= 2){
            cout << a << ":" << b << endl;
            a = b = 0;
        }
    }
    //新的一轮刚开始，或上一局没有打完
    cout << a << ":" << b << endl;
}

int main(){

    char ch;
    while(cin >> ch && ch != 'E'){
        if(ch == 'W'|| ch == 'L'){
          str[cnt ++] = ch;
        }
    }
    show(11);
    cout << endl;
    show(21);
}

[NOIP2015 普及组] 扫雷游戏

#include<bits/stdc++.h>
using namespace std;
char a[101][101]; //地图
int b[101][101] = {0}; //答案
int n, m, i, j;
int dx[8] = {1, 0, -1, 0, -1, 1, 1, -1};//方向
int dy[8] = {0, 1, 0, -1, -1, -1, 1, 1}; //方向
void dfs(int x, int y)//调用函数将地雷周围的数加起来
{
    int nx, ny, k;
    for (k = 0; k < 8; ++ k)//循环，将8个方向加起来。（不需要判断地雷，因为输出有判断）
    {
        nx = x + dx[k];
        ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)//判断有没有越界
          b[nx][ny] ++;//加一
    }
}
int main()
{
    cin >> n >> m; //输入
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
        {
            cin >> a[i][j];
            if (a[i][j] == '*')
            dfs(i,j);//如果是地雷就调用函数
        }
    for (i = 1; i <= n; ++ i)
    {
        for (j = 1; j <= m; ++ j)
            if (a[i][j] == '*')//判断是地雷就直接输出
                cout << a[i][j];
            else
                cout << b[i][j];//不是地雷输出答案
            cout<<endl;
    }
    return 0;
}

[NOIP2016 提高组] 玩具谜题

#include<bits/stdc++.h>
using namespace std;
const int N = 1E5;
struct node 
{
    int head;
    string name;
}a[N + 5];
int n, m, x, y;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i)
    {
        cin >> a[i].head >> a[i].name;
    }
    int now = 0;
    for (int i = 1; i <= m; ++ i)
    {
        // 分四种情况分析 
        cin >> x >> y;
        if (a[now].head == 0 && x == 0) now = (now + n - y) % n;
        else if (a[now].head == 0 && x == 1) now = (now + y) % n;
        else if (a[now].head == 1 && x == 0) now = (now + y) % n;
        else if (a[now].head == 1 && x == 1) now = (now + n - y) % n;
    }
    cout << a[now].name << endl;
    return 0;
}

P1601 A+B Problem（高精）

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

vector<int> add(vector<int> a, vector<int> b) {
    vector<int> ret;
    int len = min((int)a.size(), (int)b.size());
    int at = 0, i = 0;
    for (; i < len; ++ i) {
        int t = a[i] + b[i] + at;
        at = t / 10;
        ret.push_back(t % 10);
    } 
    while (i < (int)a.size()) {
        int t = a[i] + at;
        at = t / 10;
        ret.push_back(t % 10);
        ++ i;
    }
    while (i < (int)b.size()) {
        int t = b[i] + at;
        at = t / 10;
        ret.push_back(t % 10);
        ++ i;
    }
    while (at) {
        ret.push_back(at % 10);
        at /= 10;
    }
    return ret; 
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> va, vb;
    for (int i = a.size() - 1; i >= 0; -- i) va.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; -- i) vb.push_back(b[i] - '0');

    vector<int> t = add(va, vb);

    for (int i = t.size() - 1; i >= 0; -- i) cout << t[i];

    return 0;
}

P1303 A*B Problem

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

const int N = 1E5 + 5;
string a, b;
int res[N];
int main ()
{
    cin >> a >> b;
    // 倒过来，数位小的在前面 
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    // 先不考虑进位 
    for (int i = 0; i < a.size(); ++ i) {
        for (int j = 0; j < b.size(); ++ j) {
            res[i + j] += (a[i] - '0') * (b[j] - '0');
        } 
    }

    // 处理进位 
    for (int i = 0; i < a.size() + b.size(); ++ i) {
        if (res[i] > 9) {
            res[i + 1] += res[i] / 10;
            res[i] %= 10;
        }
    }

    // 输出结果 
    int len = a.size() + b.size();
    while (res[len] == 0 && len) -- len;
    while (len >= 0) cout << res[len --];

    return 0;
}

P1009 [NOIP1998 普及组] 阶乘之和

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

vector<int> add(vector<int> a, vector<int> b) {
    vector<int> ret;
    int len = min((int)a.size(), (int)b.size());
    int at = 0, i = 0;
    for (; i < len; ++ i) {
        int t = a[i] + b[i] + at;
        at = t / 10;
        ret.push_back(t % 10);
    } 
    while (i < (int)a.size()) {
        int t = a[i] + at;
        at = t / 10;
        ret.push_back(t % 10);
        ++ i;
    }
    while (i < (int)b.size()) {
        int t = b[i] + at;
        at = t / 10;
        ret.push_back(t % 10);
        ++ i;
    }
    while (at) {
        ret.push_back(at % 10);
        at /= 10;
    }
    return ret; 
}
vector<int> mul(vector<int> a, vector<int> b) {
    vector<int> ret(a.size() + b.size() + 5, 0);
    for (int i = 0; i < a.size(); ++ i) {
        for (int j = 0; j < b.size(); ++ j) {
            ret[i + j] += a[i] * b[j];
        }
    }   

    for (int i = 0; i + 1 < ret.size(); ++ i) {
        ret[i + 1] += ret[i] / 10;
        ret[i] %= 10;
    } 

    while (ret.size() > 1 && ret.back() == 0) ret.pop_back();

    return ret;

}
vector<int> get(int x) {
    vector<int> ans;
    if (x == 0) {
        ans.push_back(0);
        return ans; 
    }

    while (x) {
        ans.push_back(x % 10);
        x /= 10;
    }
    return ans;
}

vector<int> jie(int n) {
    if (n == 1) return get(1);
    return mul(get(n), jie(n - 1)); 
}

void printV(vector<int> t) {
    for (int i = t.size() - 1; i >= 0; -- i) {
        cout << t[i];
    }
    cout << endl;
}
int main() {
    int n;
    cin >> n;
    vector<int> ans = get(0);

    for (int i = 1; i <= n; ++ i) {
        ans = add(ans, jie(i));
    }

    printV(ans);

    return 0;
}

P4924 [1007] 魔法少女小Scarlet

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

const int N = 500;
int square[N + 5][N + 5],temp[N + 5][N + 5];

void spin(int x, int y, int r)//顺时针旋转90°
{
    for(int i = x - r; i <= x + r; ++ i)
    {
        for(int k = y - r; k <= y + r; ++ k)
            temp[i][k] = square[i][k];
    }
    int x1 = x + r, y1 = y - r;
    for(int i = x - r; i <= x + r; ++ i)
    {
        for(int k = y - r; k <= y + r; ++ k)
        {
            square[i][k] = temp[x1][y1];
            x1 --;
        }
        x1 = x + r, y1 ++;
    }
}

void spin_(int x, int y, int r)//逆时针旋转90°
{
    for (int i = x - r; i <= x + r; ++ i)
    {
        for (int k = y - r; k <= y + r; ++ k)
            temp[i][k] = square[i][k];
    }
    int x1 = x - r, y1 = y + r;
    for (int i = x - r; i <= x + r; ++ i)
    {
        for (int k = y - r; k <= y + r; ++ k)
        {
            square[i][k] = temp[x1][y1];
            x1 ++;
        }
        y1 --, x1 = x - r;
    }
}

int main()
{
    int n, m, t = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        for(int k = 1; k <= n; ++ k)
            square[i][k] = ++ t;
    }//首先给矩阵赋值
    int x, y, r, z;
    for (int i = 0; i < m; ++ i)
    {
        cin >> x >> y >> r >> z;
        if (z == 0)
            spin(x, y, r);
        else if (z == 1)
            spin_(x, y, r);
    }
    for (int i = 1; i <= n; ++ i)
    {
        for (int k = 1; k <= n; ++ k)
            cout << square[i][k] << " ";
        cout << endl;
    }

    return 0;
}

P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布

#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 10;
int n, na, nb, a[N], b[N], cnta, cntb;
int vs[5][5] = {{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}}; //得分表的处理 
int main()
{
    cin >> n >> na >> nb;
    for(int i = 0; i < na; i++) cin >> a[i];
    for(int i = 0; i < nb; i++) cin >> b[i];
    for(int i = 0; i < n; i++)
    {
        cnta += vs[a[i % na]][b[i % nb]]; //周期循环 
        cntb += vs[b[i % nb]][a[i % na]];
    }
    cout << cnta << " " << cntb << endl;
    return 0;
}

[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

#include<bits/stdc++.h>
using namespace std;
char m[12][12];//地图
int f[3], c[3], ans, tdz;//农夫，奶牛，秒数，专属值
bool zt[200005];//记录专属值是否出现
void move(int x, int y, int mi, int h){//移动函数
    if (mi==0){
        if (m[x-1][y]=='*') if (h==0) f[0]=1; else c[0]=1;
        else if (h==0) f[1]--; else c[1]--;
    }else if (mi==1){
        if (m[x][y+1]=='*') if (h==0) f[0]=2; else c[0]=2;
        else if (h==0) f[2]++; else c[2]++;
    }else if (mi==2){
        if (m[x+1][y]=='*') if (h==0) f[0]=3; else c[0]=3;
        else if (h==0) f[1]++; else c[1]++;
    }else{
        if (m[x][y-1]=='*') if (h==0) f[0]=0; else c[0]=0;
        else if (h==0) f[2]--; else c[2]--;
    }
}
bool pd(){ //判断循环终止条件：如果奶牛坐标与农夫坐标相等，则他们重叠，返回0，退出循环
    if (f[1]==c[1]&&f[2]==c[2]) return 0;
    else return 1;
}
int main(){
    for (int i=0;i<=11;i++) m[i][0]='*',m[i][11]='*';
    for (int i=1;i<=11;i++) m[0][i]='*',m[11][i]='*';
    for (int i=1;i<=10;i++){
        for (int j=1;j<=10;j++){
            cin>>m[i][j];
            if (m[i][j]=='F') f[1]=i,f[2]=j;
            if (m[i][j]=='C') c[1]=i,c[2]=j;
        }
    }
    while (pd()){//模拟每秒
        tdz=f[1] + f[2] * 10 + c[1] * 100 + c[2] * 1000 + f[0] * 10000 + c[0] * 40000;
        if (zt[tdz]){//死循环了就输出0并结束程序
            cout<<0<<endl;
            return 0;
        }
        zt[tdz]=1;//标记
        move(f[1],f[2],f[0],0);
        move(c[1],c[2],c[0],1);//依次移动农夫和奶牛
        ans++;//记录秒数
    }
    cout<<ans<<endl;//输出
    return 0;
}

[NOIP2009 普及组] 多项式输出

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

int main() {
    int n, a;
    cin >> n;
    for (int i = n; i >= 0; -- i) {
        cin >> a;
        if(a) {    // 判0系数
            if (i != n && a > 0) cout << "+"; //    根据正负、是否为最高此项决定加号
            if (abs(a) > 1 || i == 0) cout << a;    // 输出系数（系数不为正负1或指数为0）
            if (a == -1 && i) cout << "-";    // -1系数特判，常数项已特判
            if (i > 1) cout << "x^" << i;    // 二次及以上输出指数
            if (i == 1) cout << "x"; // 一次项
        }
    }
    return 0;
}

[NOIP2007 提高组] 字符串的展开

#include<bits/stdc++.h>
using namespace std;
int main() {

    int p1, p2, p3;
    string s;
    cin >> p1 >> p2 >> p3 >> s; 

    for (int i = 0; i < s.size(); ++ i) {
        // before, after, current
        char be, af, cur;
        cur = s[i];
        if (i > 0 && i < s.size() - 1)
            be = s[i - 1], af = s[i + 1];
        if (cur == '-' && af > be && ((be >= '0' && af <= '9') || (be >= 'a' && af <= 'z'))) {
            int j;
            for (p3 == 1 ? j = be + 1 : j = af - 1; p3 == 1 ? j < af : j > be; p3 == 1 ? ++ j : -- j) {
                char p = j; 
                if (p1 == 2) // 是否大写
                    p = (p >= 'a') ? p - 32 : p;
                else if (p1 == 3) p = '*';
                for (int k = 0; k < p2; ++ k) {
                    cout << p; 
                } 

            }           
        }else {
            cout << cur;
        }
    }

    return 0;
}

[NOIP2006 提高组] 作业调度方案

P1786 帮贡排序

P1591 阶乘数码

P1249 最大乘积

[NOIP2003 普及组] 麦森数

【1-2】排序

【1-3】暴力枚举

【1-4】递推与递归

【1-5】贪心

【1-6】二分查找与二分答案

【1-7】 搜索

洛谷题解
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
															
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

															
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
前缀和与差分

							
							

							
快速排序模板

							
							

							
洛谷GESP C++上机题

							
							

							
YS-GPT

							
							

							
洛谷官方题单【入门】

							
							

							
数位DP

							
							

							
蓝桥杯-特殊时间

							
							

							
The 2022 ICPC Asia Xian/Jinan Regional Contest\2022 ICPC 亚洲区域赛西安站和济南站题解记录

							
							

							
数学知识-常用算法模板

							
							

							
ModInt\mint  泛编程模板类