2024.6.16

2024.6.16 【执笔洇墨铸流年，仗剑酌酒碎绮梦】

Sunday 五月十一 父亲节

模拟赛

A. 正确答案

【题目描述】

小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。

“吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。

外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。这可让小Y与小H犯了难。你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。无解输出-1。

【输入格式】

第一行四个整数n, m, p, q，意义如上描述。

接下来n行，每一行m个字符’N’或’Y’，表示这题这个神犇的答案。

【输出格式】

仅一行，一个长度为m的字符串或是-1。

【样例输入】

2 2 2 0
YY
YY

【样例输出】

YY

【数据范围】

30% : n <= 100.

60% : n <= 5000 , m <= 100.

100% : 1 <= n <= 30000 , 1 <= m <= 500. 0 <= p , q 且 p + q <= n.

考场上HASH打炸了

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

int n,m,p,q;
string s[30003];

int score(string an,string ju){
    if(an==ju)
        return 1;
    for(int i=0;i<m;i++)
        if(an[i]==ju[i])
            return 3;
    return 2;
}

bool cmp(string p,string q) { return p<q; }

bool pd(string ss,int ri){
    if(ri!=p) return 0;
    int mark;
    int out1=0,out2=0,out3=0;
    for(int i=1;i<=n;i++){
        int mark=score(ss,s[i]);
        if(mark==1) out1++;
        if(mark==2) out2++;
        if(mark==3) out3++;
    }

    if(out1==p && out2==q && out3==n-p-q)
        return 1;
    return 0;
}

string ans(){
    int tot=1;
    for(int i=1;i<=n;i++){
        if(s[i]==s[i+1])
            tot++;
        else{
            int flag=pd(s[i],tot);
            tot=1;
            if(flag==1)
                return s[i];
        }
    }
    return "-1";
}

int main(){
    scanf("%d%d%d%d\n",&n,&m,&p,&q);
    for(int i=1;i<=n;i++)
        cin>>s[i]; 
    sort(s+1,s+n+1,cmp);
    cout << ans();
    return 0;
}

B. 无线通讯网

【题目描述】

国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所（两边都拥有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过D，这是受收发器的功率限制。收发器的功率越高，通话距离D会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个D。

你的任务是确定收发器必须的最小通话距离D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

【输入格式】

第1行：2个整数S（1<=S<=100）和P（S<P<=500），S表示可安装的卫星电话的哨所数，P表示边防哨所的数量。

接下里P行，每行描述一个哨所的平面坐标（x,y），以km为单位，整数，0<=x,y<=10000。

【输出格式】

第1行：1个实数D，表示无线电收发器的最小传输距离。精确到小数点后两位。

【样例输入】

2 4
0 100
0 300
0 600
150 750

【样例输出】

212.13

数据范围

对于20%的数据 P=2，S=1

对于另外20%的数据 P=4，S=2

对于100%的数据 1<=S<=100，S<P<=500

最小生成树，

去掉前s-1条边取最大就是答案

//2024.6.16
//by white_ice
#include<bits/stdc++.h>
//#include"fopen.cpp"
using namespace std;
#define itn int
constexpr int oo= 503;

itn s,p;
itn x[oo],y[oo];

struct nod{itn x,y;double w;}st[oo*oo];
int top;
int cmp(nod a,nod b){return a.w<b.w;}

int fa[oo];
int find(itn x){while (x!=fa[x])x=fa[x]=fa[fa[x]];return x;}

__inline double out(itn i,itn j){return sqrt((double)((x[i]-x[j])*(x[i]-x[j]))+(double)((y[i]-y[j])*(y[i]-y[j])));}

nod ans[oo];itn cet;
itn cnt;

signed main(){
    //fre();

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

    cin >> s >> p;

    for (itn i=1;i<=p;i++)
        cin >>  x[i] >> y[i];
    
    for (itn i=1;i<=p;i++){
        for (int j=i+1;j<=p;j++){
            st[++top].x = i;
            st[top].y = j;
            st[top].w = out(i,j);
        }
    }   
    sort(st+1,st+top+1,cmp);

    for (int i=1;i<=p;i++)
        fa[i] = i;
    
    for (int i=1;i<=top;i++){
		int eu=find(st[i].x);
        int ev=find(st[i].y);
		if (eu == ev)
            continue;
		fa[ev]= eu;
		ans[++cet] = st[i];
		cnt++;
		if (cnt==p-1)
            break;
	}
    sort(ans+1,ans+cet+1,cmp);
    if (s==0)
        printf("%.2lf",ans[cet].w);
    else  printf("%.2lf",ans[cet-s+1].w);

    return 0;
}

C. 序列问题

【题目描述】

小H是个善于思考的学生，她正在思考一个有关序列的问题。

她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。

这两个集合要满足以下的条件：

1. 两个集合中的元素都为整数，且都在 [1, n] 里，即Si，Ti ∈ [1, n]。

2. 对于集合S中任意一个元素x，集合T中任意一个元素y，满足x < y。

3. 对于大小分别为p, q的集合S与T，满足

   a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2] and a[t3] ... and a[tq].
   

小H想知道一共有多少对这样的集合(S,T)，你能帮助她吗？

【输入格式】

第一行，一个整数n

第二行，n个整数，代表ai。

【输出格式】

仅一行，表示最后的答案。

【样例输入】

4
1 2 3 3

【样例输出】

4

【样例解释】

S = {1,2}, T = {3}， 1 ^ 2 = 3 = 3 (^为异或)

S = {1,2}, T = {4}, 1 ^ 2 = 3 = 3

S = {1,2}， T = {3，4} 1 ^ 2 = 3 & 3 = 3 （&为与运算）

S = {3}， T = {4} 3 = 3 = 3

【数据范围】

30%: 1 <= n <= 10

60%: 1 <= n <= 100

100%: 1 <= n <= 1000, 0 <= ai < 1024

抽象DP，

三维DP加压位高精

根本就不是给人打的

最后 $$ f [ 1 ] [ 0 ] [ 2 ] f[ 1 ][ 0 ][ 2 ] f[ 1 ][ 0 ][ 2 ] $$ 就是答案

还需要用到滚动数组

D. 小K的农场

【题目描述】

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

【输入格式】

第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息数目。

接下来m行：

如果每行的第一个数是1，接下来有3个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物。

如果每行的第一个数是2，接下来有3个整数a,b,c，表示农场a比农场b至多多种植了c个单位的作物。

如果每行第一个数是3，家下来有2个整数a,b，表示农场a终止的数量和b一样多。

【输出格式】

如果存在某种情况与小K的记忆吻合，输出“Yes”，否则输出“No”。

【样例输入】

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

【样例输出】

Yes

样例解释：

三个农场种植数量可以为(2,2,1)。

对于100%的数据 1<=n,m,a,b,c<=10000.

查封约束的板子，

校内oj卡我TLE可恶啊

//T4
#include<bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;
int l[N],r[N];

struct node
{
    int v,w;
};

vector<node>q[N];

bool Spfa(int u)
{
    r[u] = 1;
    for(int i = 0;i < q[u].size();i ++)
    {
        int ll = q[u][i].w;
        int rr = q[u][i].v;
        if(l[rr] > l[u] + ll)
        {
            l[rr] = l[u] + ll;
            if(r[rr]) return 0;
            if(!Spfa(rr)) return 0;
        }
    }
    r[u] = 0;
    return 1;
}

int main()
{
    cin >> n >> m;
    while(m --)
    {
        int op,a,b,c;
        cin >> op;
        if(op == 1)
        {
            cin >> a >> b >> c;
            q[a].push_back((node){b,-c});
        }
        else if(op == 2)
        {
            cin >> a >> b >> c;
            q[b].push_back((node){a,c});
        }
        else
        {
            cin >> a >> b;
            q[a].push_back((node){b,0});
            q[b].push_back((node){a,0});
        }
    }
    for(int i = 1;i <= n;i ++) 
        l[i] = 0x3f3f3f;
    for(int i = 1;i <= n;i ++) 
        q[0].push_back((node){i,0});
    if(Spfa(0)) cout << "Yes";
    else cout << "No";
    return 0;
}