也想过用数组存储人数【9159.com】,若当前人的答

作者: 编程  发布:2019-08-30

POJ 2576 Tug of War

刚开始一直在纠结怎么记录人数,因为一开始的想法是dp[i][j]表示前i个人是否能达j这个值,想过用状态压缩存储路径,然后发现状态压缩只适合在人数<20时,时间和空间复杂度才可以接受,也想过用数组存储人数,但也不好操作,看了别人的解题报告,才发现自己想太多了,这里根本不需要知道路径,只需要知道到达j这个值时,有多少个人就可以了。所以直接加一个状态表示人数,于是状态就变成了:dp[i][k][j]表示前i 个人时,选k个人时,是否能到达j值

然后考虑到空间复杂度,省略i这个状态,用逆序保证每个人只选一次

 

#include 
#include
int dp[105][45005],w[105];
int n;
void init(){
 memset(dp,0,sizeof(dp));
 dp[0][0]=1;
}
int main(){
 #ifndef ONLINE_JUDGE
 freopen("in.txt","r",stdin);
 #endif
 scanf("%d",&n);
 int sum=0;
 for(int i=1;i<=n;i  ) {
  scanf("%d",&w[i]);
  sum =w[i];
 }
 init();
 for(int i=1;i<=n;i  ){
  for(int j=sum;j-w[i]>=0;j--){
   for(int k=n/2 1;k>=1;k--){
    if(dp[k-1][j-w[i]]) {
     dp[k][j]=dp[k-1][j-w[i]];
    }
   }
  }
 }
 for(int i=sum/2;i>=0;i--){
  if(n&1) {
   if(dp[n/2][i]||dp[n/2 1][i]) {
    printf("%d %dn",i,sum-i);
    break;
   }
  }
  else{
   if(dp[n/2][i]) {
    printf("%d %dn",i,sum-i);
    break;
   }
  }
 }
 return 0;
}

 

2576 Tug of War 刚开始一直在纠结怎么记录人数,因为一开始的想法是dp[i][j]表示前i个人是否能达j这个值,想过用状态压缩存储路径,然后...

前言

正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。
如何从这篇文章受益?

先看题目大意,对照Example的样例理解题目意思;
尝试解答,得到自己的答案,并分析时间和空间复杂度
思考完毕,看题目解析,对比分析自己解法的异同和优劣。

题目大都是LeetCode的hard难度。

A Nintendo Switch生产车间

解题思路:

一眼看上去以为是流水线问题,其实不然,切换流水线不需要时间,因此对于每个工序,只要找到消耗时间最短的一条流水线去完成即可。使用线性查找或第k大数求最小值的时间复杂度都是线性的,因此总的时间复杂度为O(mn),空间复杂度为O(mn).

代码:


#include <iostream>
#include <algorithm>

using namespace std;

const int MaxN = 1023, MaxM = 1023;
long long ans;
int T, n, m;
int t[MaxM][MaxN];

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    for (int K = 1; K <= T; K  ) {
        cin >> n >> m;
        for (int i = 0; i < n; i  )
            for (int j = 0; j < m; j  )
                cin >> t[j][i];     
                   //以工序为第一维,同一工序的数据都是相邻的,方便使用STL
        ans = 0;
        for (int i = 0; i < m; i  ) {
            nth_element(t[i], t[i], t[i]   n);  //求每个工序耗时最小值
            ans  = t[i][0];
        }
        cout << "Case #" << K << ": " << ans << "n";
    }
}

 

2016-11-14试题解题报告

正文

41.First Missing Positive
题目链接
题目大意:
给出一个数组,找到数组中没有的最小正整数。
要求:O(N)的时间和O(1)的空间复杂度;

Example
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

** 题目解析:**
先不考虑题目要求的时间、空间复杂度;
暴力的做法有两个:
1、时间最快,空间不限:数组a[N],然后出现数字k就a[k]=1标志出现;
2、时间、空间都不限:排序,遍历一遍数组;

回到题目的要求,时间复杂度要求是O(N),可以肯定是会用到方法1;
现在要求O(1)的空间复杂度,那么就必须利用上给出的数组。
遍历数组,如果数字k小于n且非负,那么a[k-1]=k-1;
然后遍历一遍,a[i] != i的就行是解。

** 复杂度解析:**
O(N)的时间和O(1)的空间复杂度;
** 其他解法:**
基数排序。

从低位开始,
当前第i位,统计0出现x次,1出现y次,(x y == n)
再次扫描数组,可以直接确定每个数字该排在哪里。
if bit = 0 then
idx = total_y (total_x-left_x)
....
基数排序解法

45. Jump Game II
题目链接
**题目大意: **
给出一个数组,数组上的值表示能前进的距离;
现在从pos=0的位置向右出发,问最少需要走几步才能到达终点。

Example
输入 A = [2,3,1,1,4]
返回 2
因为可以从pos=0走到pos=1,然后直接到达pos=4;

题目解析:
第一反应就是bfs,但是bfs需要每次判断距离[i 1, i k]内的点是否访问,导致时间复杂度是O(N^2);
这个题也可以用动态规划:
dp[i]表示到达i的最短步数;
那么状态方程可以写成dp[i k]=min(dp[i k], dp[i] 1); k∈[1, nums(i)]
这样对于每个i都需要去更新后面nums[i]状态,故而复杂度也是O(N^2);
对状态转移方程稍作修改:
dp[i] = min(dp[i], dp[k] 1); k num[k] >= i 且 k < i
这样可以建一个dp[i]的优先队列,先按照步数排序,再按能到达的距离排序;
每次从队列的顶端拿出步数最小的dp值,判断pos的有效区间是否覆盖当前位置i;
如果不覆盖,那么对i 1必然也不覆盖,可以丢弃;
如果覆盖,则直接dp[i]=dp[k] 1,并把(dp[i],i nums[i])放入优先队列;
复杂度是O(NlogN)。

提交后,非常遗憾的收获TLE...

仔细观察dp[i]的性质,可以得出一个结论:
步数越大,能到达的距离就越远;
那么先建一个队列,保证步数最小的在前面,后面是步数大但是覆盖距离较远的备选;
这样可以O(1)取出最优解;
并且可以设定一个maxRight,表示队列当前最远的覆盖距离,如果没有大于这个数字,可以不用放入队列;
这样可以在O(N)的时间/空间复杂度解决问题。

** 复杂度解析: **
O(N)的时间/空间复杂度解决问题。

84. Largest Rectangle in Histogram
题目链接
** 题目大意:**
给出一个数组,数组a[i]表示第i栋楼的高度;
求出最大矩形的面积。

example,
Given heights = [2,1,5,6,2,3],
return 10。

样例的图

最大的面积

题目解析:
维护一个高度不减少的栈,每次可以通过栈,快速得出面积。

** 复杂度解析:**
时间复杂度是O(N)
空间复杂度是O(N)

** 代码量:**

int largestRectangleArea(vector<int>& heights) {
        int ret = 0;
        heights.push_back(0);
        stack<int> s;
        for (int col = 0; col < heights.size();   col) {
            while (!s.empty() && heights[col] < heights[s.top()]) {
                int top = s.top();
                s.pop();
                int area = heights[top] * (s.empty() ? col : (col - s.top() - 1));
                ret = max(ret, area);
            }
            s.push(col);
        }
        return ret;
    }

85. Maximal Rectangle
题目链接
** 题目大意:**
给出一个01矩阵,求全为1的最大的矩形的面积;

For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.

最大面积如上,为6

** 题目解析:**
假设最后的矩形是(i, j)到(x, y),01矩阵为n*m矩阵;
从1到n枚举y,那么要求变成矩形贴着底边,然后面积尽可能大。
把与底部连着的1统计起来,例如当row=3的时候,分别为[3,1,3,2,2];
此时,题目与84. Largest Rectangle in Histogram完全一致;
维护一个高度不减少的栈,每次可以通过栈,快速得出面积。

** 复杂度解析:**
时间复杂度是O(N)
空间复杂度是O(N)

97. Interleaving String
题目链接
题目大意:
给出三个字符串s1,s2,s3;
判断字符串s3能否由字符串s1和s2组成,要求s1的字符串内字符的相对顺序不变,s2同理。(假如s1=abc,那么在s3中,就不能变成bac,相对顺序必须是abc)

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

** 题目解析:**
动态规划。
dp[i][j] 表示s1的前i个字符,s2的前j个字符,组成的字符串是否为s3的前i j个字符。
dp[0][0]=true,表示初始状态。
假设dp[i][j]=true,那么表示s1的前i个字符,s2的前j个字符,与s3的前i j个字符是匹配的。
那么只要s1[i 1]==s3[i j 1],那么dp[i 1][j]=true;
同理,有dp[i][j]=true && s2[j 1] == s3[i j 1] => dp[i][j 1]=true

9159.com,最后看dp[n][m]是否为true即可。

** 复杂度解析:**
时间和空间复杂度是O(NM) N是s1长度,M是s2长度;

*** 135. Candy ***
题目链接
** 题目大意:**
n个人排成一行,每个人有一个rating的数值。
现在给所有人分配糖果,要求:
1、每个人至少有一个;
2、rating比身边人高的分配到更多的糖果。
问最少需要多少糖果。

题目解析:
假设所有人rating一致,那么需要n个糖果;
如果有一人rating更高,那么需要n 1;
如果有2人rating更高,则看两个人是否相邻,需要n 2或n 3个糖果;
以此,可以得出一种分配方案:
从最小的rating值开始分配,每次观看旁边的人是否有糖果:
如果身边人有糖果,则分配max(左边, 右边) 1;
如果身边人没有糖果,则分配1;
时间复杂度为O(NLogN),排序耗时。

收获一枚TLE;
那么对算法进行优化。
根据分配糖果的条件2,我们知道在一个单调递增中:(单调递减可以逆着看,就是单调递增)
分配的结果是1、2、3、4、5这样的序列;
那么,一个数组可以分成多个单调递增的序列;
然后反着遍历,找到单调递减的序列;
剩下的部分可以全部填1。

复杂度解析:
时间复杂度是O(N)
空间复杂度是O(N)

B I have atree

解题思路:

非常明显就是“数字三角形”的马甲版,经典的DP题目。

遍历一遍三角形,对于每个位置,记录的是从起点到这个位置的分值的和的最大值。

边缘位置的到达路径是唯一的,只要依次累加即可得到这个位置的分值。除边缘位置外,每个数字都只能由上一行的两个固定数字走到,由上向下遍历,每次都选择两个局部和中较大的一个,遍历结束后,最后一行中最大的一个数即为答案。

时间复杂度:O(n^2),空间复杂度:O(n^2)

代码:


#include <iostream>
#include <cstring>
using namespace std;
const int MaxN = 1023;
int n;
long long ans;
long long num[MaxN][MaxN];
#define Max(a, b) (((a)>(b))?(a):(b))
int main() {
    ios::sync_with_stdio(false);
    while (cin >> n) {
        memset(num, 0, sizeof(num));
        for (int i = 1; i <= n; i  )
            for (int j = 1; j <= i; j  )
                cin >> num[i][j];
        for (int i = 2; i <= n; i  )
            for (int j = 1; j <= i; j  )
                num[i][j]  = Max(num[i - 1][j - 1], num[i - 1][j]);
                   //边界以外的数已经置0,因此边界的数不需要额外考虑
        ans = -1;
        for (int i = 1; i <= n; i  ) ans = Max(ans, num[n][i]);
        cout << ans << "n";
    }
}

By shenben

总结

给自己定的小目标50题,因为第一页某些题目质量较低,加了一些比较容易的目前进度33/50。

C Magry的朋友很多 - 零食篇

解题思路:

加了马甲的01背包问题。把好吃程度小于等于0的物品先去掉,剩下的物品中,价格视为weight,好吃程度视为value,手中钱数视为容量,就是一个标准的01背包模型了。

时间复杂度:O(nk),空间复杂度:O(k)

代码:


#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;
#define Max(a, b) (((a)>(b))?(a):(b))
const int MAX_W = 100000   7;
const int MAX_N = 10000   7;
ll dp[MAX_W], w[MAX_N], v[MAX_N];
ll n, W, cnt, x, _w, t;

//01背包模型
void solve() {
    memset(dp, 0, sizeof(dp));
    for (ll i = 0; i < n; i  )
        for (ll j = W; j >= w[i]; j--)
            dp[j] = Max(dp[j], dp[j - w[i]]   v[i]);
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n) {
        cnt = 0;
        for (int i = 0; i < n; i  ) {
            cin >> x >> _w >> t;
            //太难吃的直接不看了
            if (t > 0) {
                w[cnt] = x;
                v[cnt] = _w;
                cnt  ;
            }
        }
        n = cnt;
        cin >> W;
        solve();
        cout << dp[W] << "n";
    }
}

 

T1:

D LongestCommon Subsequence

解题思路:

如果是求最公共长子序列的长度,或是求一个最长公共子序列,做法非常简单,用dp[i][j]表示匹配到a[i]和b[j]时最长子序列的长度,有:

dp[i][j] = Max(dp[i - 1][j],

dp[i][j -1],

dp[i-1][j-1]|a[j]==b[j]);

      DP过程完成后,dp[len1][len2]即为最长公共子序列的长度。

      要求出所有最长公共子序列,可以对得到的dp数组进行溯源,反向找到由dp[0][0]通向dp[len1][len2]的路径,过程中每个值发生变化的点就是子序列的一个元素。事实上,在最坏情况下,每个结点都会引出两条路径,复杂度非常高,为O(2^n) 。例如,对于数据:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

除了边界之外,回溯过程中每个点都会引出两条路径。我使用了几种在OJ能通过的代码,在Intel Core i7 6700K@4.4GHz 双通道DDR4 2800MHz的平台进行测试,均未能在1min内给出结果。多谢助教高抬贵手,数据方面没有太为难我们。

在宫洁卿的论文《利用矩阵搜索求所有最长公共子序列的算法》(链接为CNKI地址)中,提出了一个(能将传统算法的指数级复杂度降低到max{O(mn),O(ck)},k为最大公共子序列的个数)的算法,使用了双栈来存储部分匹配的串的内容,但是实现较为复杂,不适合在分秒必争的上机环境内使用。

时间复杂度:O(2^n),空间复杂度:O(len1*len2)

代码:


#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;

const int MaxN = 100   7;
int len1, len2, len;
int dp[MaxN][MaxN];
set<string> ans;
char s1[MaxN] = " ", s2[MaxN] = " ";

#define Max(a,b) (((a)>(b))?(a):(b))
//DP求LCS长度
void LCS(char A[],char B[]) {
    memset(dp, 0, sizeof(dp));
    len1 = (int)strlen(A), len2 = (int)strlen(B);
    for (int i = 1; i <= len1; i  )
        for (int j = 1; j <= len2; j  ) {
            dp[i][j] = Max(dp[i - 1][j],dp[i][j - 1]);
            if (A[i] == B[j]) dp[i][j] = Max(dp[i][j],dp[i - 1][j - 1]   1);
        }
    len = dp[len1][len2];
}
//类似DFS求出所有串
void go(int i, int j, string s) {
    if (i <= 0 || j <= 0) return;
    if (s1[i] == s2[j]) {
        s.push_back(s1[i]);
        if (s.length() == len) reverse(s.begin(), s.end()), ans.insert(s);
        else go(i - 1, j - 1, s);
    } else {
        if (dp[i - 1][j] >= dp[i][j - 1]) go(i - 1, j, s);
        if (dp[i][j - 1] >= dp[i - 1][j]) go(i, j - 1, s);
    }
}

int main() {
    while (cin >> s1   1 >> s2   1) {
        LCS(s1, s2);
        ans.clear();
        go(len1, len2, "");
        for (auto s:ans)
            cout<<s<<"n";
    }
}

 

30%:  O(n ^ 2 * m)暴力判断。

E 身可死,武士之名不可弃

解题思路:

此题的原型为双调旅行商问题。

单调地从左到右一次,再从右到左一次形成一条回路,可以看作是单调地从最左点向右引出两条路线,最后在最右边的点汇合。

由于三角形两边长之和一定大于第三边,如果两条路线有重合,或者有交叉,这样形成的回路一定不是最短的。因此,两条路线除了源点和汇点外,应该是严格不重合不交叉的。

先对所有点进行从左到右的排序,定义dist[i][j]为点i到点j的几何距离,定义dp[i][j]为第一条路线走到i点,第二条路线走到j点的总路程长度,由于两条路线是相互独立的,因此可以假设一条路线总是领先另一条。此处设j<=i.

状态转移方程为:

dp[i][j] = dp[i - 1][j] dist[i -1][i]   |   j < i – 1

              Min(dp[i - 1][u] dist[u][i]), 0<=u<i– 1   |  j==i – 1

              Min(dp[i - 1][u] dist[u][i] dist[i-1][i]), 0<=u<i– 1 |  j==i

后两种转移方式最多只会触发2*n次,因此总的时间复杂度:O(n^2),空间复杂度:O(n^2)

代码:


#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>

using namespace std;

#define x first
#define y second
#define sqr(a) ((a)*(a))
#define Min(a, b) (((a)<(b))?(a):(b))
typedef long long ll;
typedef pair<ll, ll> pll;   //存点

const int MaxN = 107;
int n;
pll p[MaxN];
double dist[MaxN][MaxN];
double dp[MaxN][MaxN];

//两点间距离
inline double Dist(pll &a, pll &b) {
    return sqrt(sqr(a.x - b.x)   sqr(a.y - b.y));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n) {
        //读入,并按照x为第一关键字排序
        for (int i = 0; i < n; i  )
            cin >> p[i].x >> p[i].y;
        sort(p, p   n);

        //预处理出所有距离
        for (int i = 0; i < n; i  )
            for (int j = 0; j < n; j  )
                dist[i][j] = Dist(p[i], p[j]);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        dp[1][0] = dist[1][0];

        //状态转移
        for (int i = 2; i < n; i  ) {
            for (int j = 0; j <= i; j  ) {
                dp[i][j] = 1e20;
                if (j < i - 1)
                    dp[i][j] = dp[i - 1][j]   dist[i - 1][i];
                if (j == i - 1)
                    for (int u = 0; u < i - 1; u  )
                        dp[i][j] = Min(dp[i][j], dp[i - 1][u]   dist[u][i]);
                if (j == i)
                    for (int u = 0; u < i - 1; u  )
                        dp[i][j] = Min(dp[i][j], dp[i - 1][u]   dist[u][i]   dist[i - 1][i]);
            }
        }
        cout << fixed << setprecision(2) << dp[n - 1][n - 1] << "n";
    }
}

 

100%: 很显然答案的可能性最多只有n种,所以我们将所有人的答案按字典序排序后枚举。将每个人的答案作为正确答案来进行判断。

F Magry猎奇的省钱策略

解题思路:

此题需要一定的思考量,其实也不是很难。可以把这题套到背包模型里,将价格视为value,时间 1(不是时间本身)视为weight,要求为(总时间>=总件数)的情况下,付出的价值尽量少,可以转化为,总weight>=n的情况下,总value最小,用01背包模型求解即可。

时间复杂度:O(n^2),空间复杂度:O(n^2)

代码:


#include <iostream>

using namespace std;
#define Min(a, b)  (((a)<(b))?(a):(b))
typedef long long ll;
const ll MaxC = (ll)1e11, MaxN = 2047, INF = MaxC * MaxN;
ll n, ans, w[MaxN], v[MaxN], arr[MaxN * 2];

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n) {
        //先用INF填充dp数组
        for (ll i = 1; i <= n   MaxN; i  )
            arr[i] = INF;
        arr[0] = 0LL;
        for (ll i = 0; i < n; i  )
            cin >> w[i] >> v[i], v[i]  ;    //时间 1
        for (ll i = 0; i < n; i  )
            for (ll j = n   2000; j >= v[i]; j--)
                arr[j] = Min(arr[j], arr[j - v[i]]   w[i]); //01背包模型
        ans = INF;
        for (ll i = n; i <= n   2000; i  )
            ans = Min(ans, arr[i]);
        cout << ans << "n";
    }
}




 

由于是判断题,若当前人的答案为正确答案则零分者的答案也就确定了,那么只需统计出这两种答案的人数判断是否满足题意,即可。这一步使用字符串哈希即可解决。

 

 

T2:

30%:枚举每个数所在的集合或者不选,然后判定即可。复杂度O(n*3^n)。

60%: Dp,两个数相等就相当于两个数的xor为0。设 f[i][j][k=0..2]代表 处理到第 I 个数,     如果 k = 1代表and值为j,如果k = 2代表xor 值为 j,如果k = 0则代表一个元素都没   取。所以很容易得到方程:

f[i][j][0] = f[i 1][j][0]

f[i][j & ai][1] = f[i 1][j][1] f[i 1][j][0] f[i 1][j & ai][1]

     f[i][j ^ ai][2] = f[i 1][j][1] f[i 1][j][2] f[i 1][j ^ ai][2];

  最后f[1][0][2]就是答案, 复杂度为O(n * 1024 * 3)

  DP还可以分开用f[i][j]和g[i][j]表示前i个xor值为j,后i个and值为j的方案数,     随后枚举分界点k来求总方案数。复杂度O(n * 1024 * 3)。

100%:满分数据需要高精,答案位数较大,需要进行压位来防止TLE,因为不知道答案的     位数究竟多大,压位后高精数组仍需要开的较大一些,所以原DP的数组滚动即可。

 

 

T3:

30%:

当T<= 10000的时候,可以设 vis[i][j] 代表到达第i个点时间为j是否合法。 这样是O(T*m),可以拿到小数据。

另外的那30%:各种奇怪的骗分方法。选手自行考虑。

100%:

当T很大的时候,我们考虑 如果0 -> x -> n - 1路径时间为T,且 从x出发有一个时间为d的环,则 一定存在一个K满足 K p*d = T(至少T满足条件),这样我们就能绕着环走p次就能构成一条时间为T的路径。

显然要求的路径一定经过 0,而且在合法情况下从0号点出发一定存在一条边,否则0号点和n - 1号就是不联通的。随便取一条边时间为d, 则能构成从0号点出发的一个时间为2d的环。这样原题就化为最短路问题了,dis[i][j] 代表到达i号点,时间为 j p * 2d,最小的 j p*2d,

最后判断dis[n -1][T % 2d] 是否小于等于T即可。

实际上就是在30%的基础上缩减状态。

时间复杂度为O(m*d)。

T1代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long 
#define R register
#define debug(x) cout<<x<<"---"<<endl
inline int read(){
    R int x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3) (x<<1) ch-'0';ch=getchar();}
    return f?x:-x;
} 
const int N=30000 5;
const int M=3000 5;
string s[N];
map<string,int>ys;
string s1,t;
int n,m,p,q;
int cnt,ans;
char ss[M];
int judge(string &std,string &now){
    int res=0;
    for(int i=0;i<m;i  ) if(std[i]!=now[i]) res  ;
    return res;
}
void fanzhuan(){
    for(int slen=s1.length(),i=0;i<slen;i  ){
        s1[i]=(s1[i]=='N'?'Y':'N');
    }
    printf("%s",s1.c_str());
}
void sp(int x){
    if(x==m){
        int j,t;
        for(j=1;j<=cnt;j  ){
            if(s[j]==s1) break;
            t=judge(s1,s[j]);
            if(t==m) break;
        }
        if(j>cnt){for(int i=0;i<m;i  ) putchar(s1[i]);exit(0);}
        return ;
    }
    for(int i=0;i<2;i  ){
        s1[x]=(!i?'N':'Y');
        sp(x 1);
    } 
}
void in(){
    char ch;int l=0;
    for(ch=getchar();l<m;ch=getchar()){
        if(ch!='n') ss[l  ]=ch;
        else break;
    }
    ss[l]='\0';
}
void work(){
    int flag=0;
    for(int i=0;i<m;i  ) t ='N';
    for(int i=1;i<=n;i  ){
        for(int j=0;j<m;j  ){
            if(s[i][j]=='Y')t[j]='N';
            if(s[i][j]=='N')t[j]='Y';
        }
        int sum=ys[s[i]],tot=ys[t];
        if(sum==p&&tot==q){
            flag=i;
            break;
        }
    }
    if(flag) printf("%s",s[flag].c_str());
    else puts("-1");
}
#define name "answer"
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    n=read();m=read();p=read();q=read();
    for(int i=1;i<=n;i  ){
        in();
        for(int j=0;j<m;j  ) s[i] =ss[j];
        ys[s[i]]  ;
    }
    sort(s 1,s n 1);
    cnt=unique(s 1,s n 1)-(s 1);
    if(!p&&!q){
        sp(0);
        return 0;
    }
    if(p){work();return 0;}
    /*if(p!=0){
        for(int i=1;i<=cnt;i  ){
            if(ys[s[i]]!=p) continue;
            ans=0;
            for(int j=1,t;j<=cnt;j  ){
                if(i==j) continue;
                t=judge(s[i],s[j]);
                if(t==m) ans =ys[s[j]];
            }
            if(ans==q){
                printf("%s",s[i].c_str());
                return 0;
            } 
        }
    }*/
    else if(q){
        for(int i=1;i<=cnt;i  ){
            if(ys[s[i]]!=q) continue;
            ans=0;
            for(int j=1,t;j<=cnt;j  ){
                if(i==j) continue;
                t=judge(s[i],s[j]);
                if(t==m) ans =ys[s[j]];
            }
            if(ans==p){
                s1=s[i];
                fanzhuan();
                return 0;
            } 
        }
    }
    else puts("-1");
    fclose(stdin);
    fclose(stdout);
    return 0;
}
/*50分代码存档
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long 
#define R register
#define debug(x) cout<<x<<"---"<<endl
inline int read(){
    R int x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3) (x<<1) ch-'0';ch=getchar();}
    return f?x:-x;
} 
inline char in(){
    for(R char ch=getchar();;ch=getchar()) if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')) return ch;
}
const int N=30000 5;
string s[N];
map<string,int>ys;
string s1;
int n,m,p,q,num,nt,nf;
bool f1;
void fanzhuan(){
    for(int slen=s1.length(),i=0;i<slen;i  ){
        s1[i]=(s1[i]=='N'?'Y':'N');
    }
    printf("%s",s1.c_str());
}
#define name "answer"
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    n=read();m=read();p=read();q=read();
    for(int i=1;i<=n;i  ){
        getline(cin,s[i]);
        ys[s[i]]  ;
    }
    sort(s 1,s n 1);
    int cnt=unique(s 1,s n 1)-(s 1);
    if(p==q){puts("-1");return 0;}
    if(p<2&&q<2&&p q<n){puts("-1");return 0;}
    int zmx=0;
    for(int i=1;i<=cnt;i  ){
        if(zmx<ys[s[i]]){
            zmx=ys[s[i]];
            s1=s[i];
        }
    }
    for(int i=1;i<=cnt;i  ){
        if(zmx==ys[s[i]]){
            if(s1!=s[i]){f1=1;break;}
        }
    }
    if(zmx==p&&f1){
        num=0;
        for(int i=1;i<=cnt;i  ){
            if(ys[s[i]]==q){
                num  ;
                s1=s[i];
            }
        }
        if(num!=1){puts("-1");return 0;}
        else{fanzhuan();return 0;}
    }
    if(zmx==q&&f1){
        num=0;
        for(int i=1;i<=cnt;i  ){
            if(ys[s[i]]==p){
                num  ;
                s1=s[i];
            }
        }
        if(num!=1){puts("-1");return 0;}
        else{printf("%s",s1.c_str());return 0;}
    }
    for(int i=1;i<=cnt;i  ){
        if(ys[s[i]]==p){
            nt  ;
            s1=s[i];
        }
    }
    if(nt==1){printf("%s",s1.c_str());return 0;}
    for(int i=1;i<=cnt;i  ){
        if(ys[s[i]]==q){
            nf  ;
            s1=s[i];
        }
    }
    if(nf==1){fanzhuan();return 0;}
    else{puts("-1");return 0;}
    if(zmx!=p&&zmx!=q){puts("-1");return 0;}
    if(p>q) printf("%s",s1.c_str());
    else fanzhuan();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
*/

T2代码:

来自std

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long ll;
const int N = 1001, M = 1024, W = 1e9;
int n, cur, nxt, va, vx, p[N];

struct huge_int {
    int len, a[40];
    huge_int(): len(1) { memset(a, 0, sizeof(a)); }

    inline void operator  = (const huge_int &b) {
        b.len > len ? len = b.len : 0;
        for (int i = 1; i <= len;   i) {
            a[i]  = b.a[i];
            if (a[i] >= W)   a[i   1], a[i] -= W;
        }
        if (a[len   1])   len;
        return ;
    }

    inline void print() {
        printf("%d", a[len]);
        for (int i = len - 1; i; --i)
            printf("	d", a[i]);
        puts(""); return ;
    }
} f[2][M][3];

char ch;
int read() {
    while (ch = getchar(), ch < '0' || ch > '9');
    int res = ch - 48;
    while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10   ch - 48;
    return res;
}

int main() {
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    n = read();
    for (int i = n; i; --i) p[i] = read();
    f[0][1023][0].a[1] = 1;
    for (int i = 0; i < n;   i) {
        nxt = cur ^ 1;
        for (int j = 0; j < M;   j)
            for (int k = 0; k <= 2;   k)
                f[nxt][j][k] = f[cur][j][k];
        for (int j = 0; j < M;   j) {
            va = p[i   1] & j, vx = p[i   1] ^ j;
            f[nxt][va][1]  = f[cur][j][0]; f[nxt][va][1]  = f[cur][j][1];
            f[nxt][vx][2]  = f[cur][j][1]; f[nxt][vx][2]  = f[cur][j][2];
        }
        cur ^= 1;
    }
    f[cur][0][2].print();
    fclose(stdin); fclose(stdout);
    return 0;
}

 

 

/*30分暴力 来自sjt
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define R register
using namespace std;
const int N=1010;
int n,a[N],x[N],y[N],ans=0;
inline int read(){
    R int x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3) (x<<1) ch-'0';ch=getchar();}
    return f?x:-x;
} 
void panduan(int l1,int l2){
    int ss=a[x[1]],sss=a[y[1]];
    for(int i=2;i<=l1;i  ) ss^=a[x[i]];
    for(int i=2;i<=l2;i  ) sss&=a[y[i]];
    if(ss==sss) ans  ;
}
void dfs_j(int d[],int k,int l,int r,int l1,int l2){
    if(k>l2){panduan(l1,l2);return;}
    for(int i=l;i<=r;i  ){
        d[k]=i;
        dfs_j(d,k 1,i 1,r,l1,l2);
    }
}
void dfs_i(int d[],int k,int l,int r,int l1,int l2){
    if(k>l1){//搜索S数组完成,搜索J数组 
        dfs_j(y,1,l,r,l1,l2);
        return;
    }
    for(int i=l;i<=r;i  ){
        d[k]=i;
        dfs_i(d,k 1,i 1,r,l1,l2);
    }
}  
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i  ) a[i]=read();
    for(int i=1;i<=n;i  ){
        for(int j=1;j<=n-i;j  ){
            dfs_i(x,1,1,n,i,j);
        }
    }
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}
*/

 

T3代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
#define R register
#define pir pair<int,int>
#define debug(x) cout<<x<<"---"<<endl
inline int read(){
    R int x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3) (x<<1) ch-'0';ch=getchar();}
    return f?x:-x;
}
inline ll Read(){
    R ll x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3) (x<<1) ch-'0';ch=getchar();}
    return f?x:-x;
} 
inline char in(){
    for(R char ch=getchar();;ch=getchar()) if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')) return ch;
}
const int N=51;
const int M=201;
const int K=20001;
struct node{
    int u,v,w,next;
}e[M<<1];
int n,m,cas,len,tot,head[M];
ll T,dis1[N][K];
bool vis[N][K];
void add(int x,int y,int z){
    e[  tot].u=x;
    e[tot].v=y;
    e[tot].w=z;
    e[tot].next=head[x];
    head[x]=tot;
}
void spfa(int S){
    memset(dis1,127/3,sizeof dis1);
    memset(vis,0,sizeof vis);
    dis1[S][0]=0;
    vis[S][0]=1;
    queue<pir>q;
    q.push(make_pair(S,0));
    while(!q.empty()){
        pir t=q.front();q.pop();
        int x=t.first;
        int p=t.second;
        vis[x][p]=0;
        for(int i=head[x];i;i=e[i].next){
            int v=e[i].v;
            ll w=dis1[x][p] e[i].w;
            int c=w%len;
            if(dis1[v][c]>w){
                dis1[v][c]=w;
                if(!vis[v][c]){
                    vis[v][c]=1;
                    q.push(make_pair(v,c));
                }
            }
        }
    }
}
void Cl(){
    tot=0;
    memset(head,0,sizeof head);
}
void work(){
    Cl();
    n=read();m=read();T=Read();
    for(int i=1,x,y,z;i<=m;i  ){
        x=read();y=read();z=read();
        add(x,y,z);add(y,x,z);
    }
    if(!head[0]) puts("Impossible");
    else{
        len=10001;
        for(int i=head[0];i;i=e[i].next){
            len=min(len,e[i].w);
        }
        len<<=1;
        spfa(0);
        if(dis1[n-1][T%len]<=T) puts("Possible");
        else puts("Impossible");
    }
}
#define name "travel"
int main(){
    freopen(name".in","r",stdin);
    freopen(name".out","w",stdout);
    cas=read();
    while(cas--) work();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

 

本文由9159.com发布于编程,转载请注明出处:也想过用数组存储人数【9159.com】,若当前人的答

关键词: 9159.com