首页 > 其他分享 >2024.4.14

2024.4.14

时间:2024-04-14 17:25:06浏览次数:22  
标签:itn oo 2024.4 14 int double st return

2024.4.14 【言念君子,温其如玉。】

Sunday 三月初六


<theme = oi-"search">
<BGM = Realms>

模拟赛!!!

P1274 魔术数字游戏

就摁模搜索就行,我是实在打不下去了。考试时200行白打了

P1275 魔板

//2024.4.14
//by white_ice
#include <bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 102;
int st[oo][oo], sp[oo][oo];
int sv[oo], sk[oo];
itn n, m;

void dod(int i) {for(int j = 1; j <= m; j++)st[i][j] ^= 1;}

bool search() {
    int find[oo];
    memset(find, 0,sizeof(find));
    for(int i = 1; i <= m; i++) {
        bool fl = 0;
        for(int j = 1; j <= m; j++) {
            bool flag = 1;
            for(int k = 1; k <= n; k++)
                if(st[k][i] != sp[k][j]) {
                    flag = 0;
                    break;
                }

            if(!find[j] && flag) {
                find[j] = i;
                fl = 1;
                break;
            }
        }
        if(!fl) return 0;
    }
    return 1;
}

bool check(int p) {
    int find[oo];
    memset(find, 0, sizeof(find));
    for(int i = 1; i <= m; i++) {
        bool fl = 0;
        for(int j = 1; j <= m; j++) {
            bool flag = 1;
            for(int k = 1; k <= p; k++)
                if(st[k][i] != sp[k][j]) {
                    flag = 0;
                    break;
                }

            if(!find[j] && flag) {
                find[j] = i;
                fl = 1;
                break;
            }
        }
        if(!fl) return 0;
    }
    return 1;
}

bool flg;
void dfs(int p) {
    if(flg == 1) return;
    if(p == n+1) {
        flg = search();
        return;	
    }
    dfs(p+1);
    if(sv[p] == m / 2) {
        dod(p);
        if(check(p))
        	dfs(p+1);
    }
}

int t;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n >> m;
        memset(sv, 0, sizeof(sv));
        memset(sk, 0, sizeof(sk));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) {
                cin >> st[i][j];
                sv[i] += st[i][j];
            }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) {
                cin >> sp[i][j];
                sk[i] += sp[i][j];
            }

        bool flag = 1;
        for(int i = 1; i <= n; i++)
            if(sv[i] + sk[i] == m)
                dod(i);
            else if(sv[i] != sk[i]) {
                flag = 0;
                break;
            }
        if(!flag)puts("NO");
        else if(search())puts("YES");
        else if(!(m%2)){
            flg = 0;
            dfs(1);
            if(flg) puts("YES");
            else puts("NO");
        } else puts("NO");
    }

    return 0;
}

我们发现对于这个操作一,对于一列,多次操作是无效的,所以我们操作之后,只考虑交换列,能不能达到目标状态就可以。

然后接着搜就好了。。。

收集雪花

题目描述
不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来,作为礼物送给在南方的同学们。一共有 n 个时刻,给出每个时刻下落雪花的形状,用不同的整数表示不同的形状。在收集的过程中,同学们不希望有重复的雪花。你可以从任意 a 时刻开始,在 b 时刻停止。a 到 b时刻中间的雪花也都将被收集。他们希望收集的雪花最多。
输入格式
第一行一个正整数 n;
第 2 行 n 个非负整数表示 n 个时刻雪花的形状。

输出格式
最多能收集雪花的数量。

样例
输入数据 1

5
1 2 3 2 1

输出数据 1

3

数据范围与提示
对于 97 分的数据,$$ 1<=n<=106,0<=x_i<=108$$。(为原始数据)

应用户要求,加入 3分的数据,$$1<=n<=106,0<=x_i<=109$$。

//2024.4.14
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 1000006;

int jntm(itn a,int b){return a>b?a:b;}
int ngm (itn a,int b){return a<b?a:b;}

int st[oo];

map<int,int>mp;
int f[oo];
int ans;

int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> st[i];
    }

    for (int i=1;i<=n;i++){
        if (mp[st[i]])
            f[i] = ngm(i - mp[st[i]],f[i-1]+1);
        else f[i] = f[i-1]+1;
        mp[st[i]] = i;
        ans = jntm (ans,f[i]);
    }
	cout << ans;
	return 0;
}

题意清晰易懂,只要一个最长不重复子序列就可以了。

使用DP求解,设f[x]为以x结尾的最长串,用map记录上一次该元素出现位置,如果没出现过直接加一,出现过就在上一次加一和当前位置减去上一次出现位置的长度中取小值.

AcWing 102. 最佳牛围栏

//来自acwing,https://www.acwing.com/user/myspace/index/360765/
#include<bits/stdc++.h>
using namespace std;
int a[100010],n,f;
double sum[100010];
bool check(double ave){
    for(int i=1;i<=n;i++){//求前缀和
        sum[i]=sum[i-1]+a[i]-ave;
    }
    double mins = 0;int j;//双指针进行扫描
    for (int i = f, j = 0; i <= n; i ++, j ++ )
    {
        mins = min(mins, sum[j]);
        if (sum[i] - mins >= 0) return true;
    }

    return false;
}
int main(){
    cin>>n>>f;
    double l=0,r=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        r=max(r,(double)a[i]);
    }
    while(r-l>1e-12){//实数二分
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%d\n", (int)(r * 1000 + 1e-3));//下取整
    return 0;
}

我自己的TLE了。。。

//2024.4.14
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn long long
#define int long long
const int oo = 100005;

itn jntm(itn a,itn b){return a>b?a:b;}
double bigg(double a,double b){return a>b?a:b;}

itn st[oo];
int sum[oo];
itn n,f;

itn cuout[oo];
int cnt = 0;

double out;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> f;
    for (itn i=1;i<=n;i++){
        cin >> st[i];
        sum[i] = sum[i-1]+st[i];
    }


    for (itn i=f;i<=n;i++){
        int big = 0;
        for (int j=i;j<=n;j++)
            big = jntm (big,sum[j]-sum[j-i]);
        //cout << big/i <<  ' ';
        double t = big;
        cuout[i] = big/i;
        out = bigg(out,(t/i));
    }

    //for  (int i=1;i<=n;i++)
      //  cout << cuout[i] << ' ';

    int ans = out*1000;


    cout << ans;

    return 0;
}

使用前缀和维护,求解对于k长度个数下的最大平均值,直接$$n^2$$爆搜会t,所以加个二分过。

标签:itn,oo,2024.4,14,int,double,st,return
From: https://www.cnblogs.com/white-ice/p/18134382

相关文章

  • 2024/4/14
    目前大盘还是很弱势,没有企稳的迹象,短线方面很多一日游,比较强的有黄金 电力工程机械 旅游  目前手上有东方电气和中润资源东方电气60日线大阳线突破,但是第一天冲高回落,第二天也是冲高回落,好在收了阳线,这种走势也算不上太强势,周一的走势不明朗中润资源周五脑袋一热接回来......
  • 2024年4月14日-UE5-时间膨胀、慢动作、切换地图、刷BOSS
    把BOSS变大一点 打开我的游戏基础,蓝图里新建一个数组的变量,用来监控场上所有的敌人是否被击杀 打开怪物总类,在所有怪物初始化之后放入数组,死亡后移出数组,数组为空就召唤Boss 在我的游戏基础蓝图里,新建一个自定义事件 回到怪物总类里,再怪物死亡后,添加一个序列怪物......
  • 汇编语言简易教程(14):中断与恢复
    汇编语言简易教程(14):中断与恢复从一般意义上讲,中断是工作流的暂停或保持。例如,如果您正在打电话,门铃响了,则电话通话将处于暂停状态,门将应答。销售人员被送走后,电话交谈恢复(对话中断的地方)在计算机编程中,中断也是当前正在执行的过程的暂停或保持。通常,当前进程会中断,以便可......
  • TC14.3 和AWC6.3 开发环境配置
    1.安装TC14.3和AWC14.3.6虚拟机,完成后,可以正常访问AWC客户端2.下载并安装nodejs和vscode2.1检查nodejs 2.2启动vscode3.从服务器将stage文件拷贝到开发目录中4.修改initenv.cnd 5.启动cmd或pshell5.1切换到开发目录cd D:\APPS\stage执行:D:\APPS\stage>initen......
  • q3-瞎汤姆养-2024.4.14
    第一批买的黑水虻孵化卵的时候没管理好,人为的搞死了,然后又买了一批,这批感觉活了点,这批是4月6日买的。不过看在鸡粪里不是特别活跃,是不是温度太高或者太低了,这个我不太知道。主要还是后期管理需要弄家里一直不给我地方搞,这个还需要空间才能玩得转,还要防止它跑出去,成虫是会飞的。......
  • 2024.4.13 模拟赛总结
    坑点总结:1.关于数据顺序模拟赛T1题面清明节,又称祭祖节,在每年4月4日至6日之间,是祭祀、祭祖和扫墓的节日。小明的爸爸妈妈决定清明假期带着他回老家扫墓。小明的爸爸一共要开车行驶1000千米才能到家,现在沿途有N个旅馆,为了安全起见,每天晚上都不开车,住在旅馆里(晚上不可以......
  • 14.lua模块(多文件)
    导入其他模块用:require("文件路径,注意去掉后缀");小括号本身可以省略,即:require"文件路径,注意去掉后缀名"如:现在有如下文件模块model.lua,代码如下:calArea={}calArea.pi=3.14--计算三角形面积functioncalArea.triangle(w,h) return0.5*w*hend--计算矩形......
  • 14、web 中间件加固-Tomcat 加固
    1.用户配置如果不需要控制台管理,请更改控制台用户文件注销账号信息;如果需要,请更改账户信息修改tomcat/conf/tomcat-user.xml文件注释或修改如下信息<rolerolename="manager-gui"/><userusername="admin"password="ABCabd123!"roles="manager=gui"/>2.开启tomca......
  • P1480 A/B Problem
    P1480A/BProblem题目描述输入两个整数\(a,b\),输出它们的商。输入格式两行,第一行是被除数,第二行是除数。输出格式一行,商的整数部分。样例输入102输出5提示\(0\lea\le10^{5000}\),\(1\leb\le10^9\)。思路通过题目数据范围可以发现是高精度除以单精度的题目......
  • P2142 高精度减法
    P2142高精度减法题目高精度减法。输入两个整数\(a,b\)(第二个可能比第一个大)。输出结果(是负数要输出负号)。样例输入21输出1提示\(20\%\)数据\(a,b\)在longlong范围内;\(100\%\)数据\(0<a,b\le10^{10086}\)。思路根据题意,数据最大范围是\(10^{1008......