损坏的RAID5

string讀入卡cin

関同步 ios::sync_with_stdio(false)

由塊號映射到具體位置

塊號id對應第col個字符串

字符串開始的位置st

  1 #include<iostream>
  2 #include<string>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue>
  7 using namespace std;
  8 int n,s,l;
  9 bool vis[1005];
 10 string t[1005];
 11 int calraw(int id)
 12 {
 13     return id/(s*(n-1));
 14 }
 15 int calcol(int id)
 16 {
 17     int st = (n-calraw(id)%n)%n;
 18     id -= (id/((n-1)*s))*(n-1)*s;
 19     int ans = (st + id/s)%n;
 20    // cout<<st<<" stid "<<id<<endl;
 21     return ans;
 22 }
 23 int st(int id)
 24 {
 25     int r=calraw(id);
 26     int ans=r*8*s+8*(id%s);
 27     return ans;
 28 }
 29 int ati(char c)
 30 {
 31     if(c>='A'&&c<='Z')
 32     return c-'A'+10;
 33     else return c-'0';
 34 }
 35 char ita(int x)
 36 {
 37     if(x>=10)
 38     return char(x-10+'A');
 39     else return char('0'+x);
 40 }
 41 string Xor(string s,string t)
 42 {
 43     string ans="";
 44     for(int i=0;i<8;i++){
 45          int a = ati(s[i]);
 46          int b = ati(t[i]);
 47          ans.append(1,ita(a^b));
 48     }
 49     return ans;
 50 }
 51 int main()
 52 {
 53      ios::sync_with_stdio(false);
 54      cin>>n>>s>>l;
 55     int id;
 56     for(int i=0;i<l;i++){
 57         cin>>id;
 58         cin>>t[id];
 59         vis[id]=1;
 60     }
 61     int len=t[id].length();
 62     int m;
 63     cin>>m;
 64    
 65     for(int i=0;i<m;i++){
 66           cin>>id;
 67           int x=calcol(id);
 68           if(vis[x]){
 69               int y =st(id);
 70               if(y>=len){
 71                   cout<<"-
";
 72                   continue;
 73               }
 74               for(int i=y;i<y+8;i++){
 75                   cout<<t[x][i];
 76               }
 77               cout<<'
';
 78           }else if(!vis[x]&&l==n-1){
 79                 int y =st(id);
 80                 string S="",T;
 81                 if(y>=len){
 82                   //puts("-");
 83                   cout<<"-
";
 84                   continue;
 85                 }
 86               
 87                 for(int i=0;i<n;i++){
 88                     if(vis[i]){
 89                         if(S==""){
 90                            S=t[i].substr(y,8);
 91                         }else{
 92                             T=t[i].substr(y,8);
 93                             S=Xor(S,T);
 94                         }
 95                     }
 96                 }
 97                 cout<<S<<'
';
 98           }
 99           else{
100               cout<<"-
";
101           }
102     }
103 
104 }
105 /**
106 3 2 2
107 0 000102030405060710111213141516172021222324252627
108 1 A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7
109  2 1 2
110 0 000102030405060710111213141516172021222324252627
111 1 000102030405060710111213141516172021222324252627
112 */

90分代碼：

由其餘已知的n-1個字符串預處理推出其餘一個字符串

查詢O(1)

預處理TLE了

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include<cstring>
#include<cstdlib>
using namespace std;

int n, s, l;
bool vis[2005];
string t[2005];
int calraw(int id)
{
    return id / (s * (n - 1));
}
int calcol(int id)
{
    int st = (n - calraw(id) % n) % n;
    id -= (id / ((n - 1) * s)) * (n - 1) * s;
    int ans = (st + id / s) % n;
    return ans;
}
int st(int id)
{
    int r = calraw(id);
    int ans = r * 8 * s + 8 * (id % s);
    return ans;
}
int ati(char c)
{
    if (c >= 'A' && c <= 'Z')
        return c - 'A' + 10;
    else
        return c - '0';
}
char ita(int x)
{
    if (x >= 10)
        return char(x - 10 + 'A');
    else
        return char('0' + x);
}

bool tmp[16];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>s>>l;
    int id;
    for (int i = 0; i < l; i++)
    {
        cin >> id;
        cin >> t[id];
        vis[id] = 1;
    }
    int len = t[id].length();
    if (l == n - 1)
    {
        string ss="";
        int res=0;

        for (int j = 0; j < len; j++)
        {
            memset(tmp,0,sizeof tmp);
            for (int i = 0; i < n; i++)
            {
                  if(vis[i]&&t[i][j]>='A'&&t[i][j]<='Z'){
                      tmp[t[i][j]-'A'+10]+=1;
                      tmp[t[i][j]-'A'+10]%=2;
                  }else if(vis[i]){
                      tmp[t[i][j]-'0']+=1;
                      tmp[t[i][j]-'0']%=2;
                  }else if(!vis[i]){
                      res=i;
                  }
            }
            int cnt=0;
            for(int k=0;k<16;k++){
                if(tmp[k])cnt^=k;
            }
            ss.append(1,ita(cnt));
            
        }
        vis[res]=1;
        t[res]=ss;

    }
    int m;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin>>id;
        if(id>=(n-1)*s*(len/(8*s))){
            cout<<"-
";
            continue;
        }
        int x = calcol(id);
        //cout<<x<<endl;
        if (vis[x])
        {
            int y = st(id);
            //  cout<<y<<endl;
            if (y >= t[x].length())
            {
                cout<<"-
";
                continue;
            }
            for (int i = y; i < y + 8; i++)
            {
                cout<<t[x][i];
            }
            cout<<"
";
        }
        else
        {
            cout<<"-
";
        }
    }
}
/**
3 2 2
0 000102030405060710111213141516172021222324252627
1 A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7
 2 1 2
0 000102030405060710111213141516172021222324252627
1 000102030405060710111213141516172021222324252627
*/