列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[lini]

題目說明 :
給你一條巨集指令 (只有加法, 乘法)
請計算最多可拿掉幾對括號(而不影響其值)

測資範圍 :
T筆測資 (T<=100)
需要考慮的字串部分 長度L<=40

題目解法 :
DFS(Depth First Search)
把字串想成一棵樹 把括號想成一個點
意思就像是大括號裡面有多個中括號, 中括號裡面有多個小括號 (有點連枝出去的感覺)
利用DFS遍歷這棵樹
單獨考慮每一層
如果一括號旁邊(左或右)有*號 則此括號不能拆 反之則可
時間複雜度 : O(T * L^2)~O(T * L^3) .. 不太會估 .. (好想睡覺 ...OTZ)

參考程式 :

代碼: [選擇]

#include <iostream>

using namespace std;

char s[100];
int st, e, ans;

int findleft(int pos){
    int i;
    for( i=pos-1; i>=st; i-- )
    {
        if( s[i]=='(' )
            return -1;
        if( s[i]==' ' )
            return i-1;
    }
    return -1;
}

int findright(int pos){
    int i;
    for( i=pos+1; i<=e; i++ )
    {
        if( s[i]==')' )
            return -1;
        if( s[i]==' ' )
            return i+1;
    }
    return -1;
}

int findMatch(int pos){
    int i, t=1;
    for( i=pos+1; i<=e; i++ )
    {
        if( s[i]=='(' ) t++;
        else if( s[i]==')' ) t--;
        if( t==0 ) return i;
    }
    return -1;
}

void DFS(int a, int b){
    int i, j, tmp, tmp2, tadd;
    for( i=a; i<=b; i++ )
    {
        if( s[i]=='(' )
        {
            tadd=1;
            tmp2=findMatch(i);
            DFS(i+1, tmp2-1);
           
            tmp=findleft(i);
            if( tmp!=-1 )
                if( s[tmp]=='*' )
                    tadd=0;
            tmp=findright(tmp2);
            if( tmp!=-1 )
                if( s[tmp]=='*' )
                    tadd=0;
            ans+=tadd;
           
            i=tmp2;
        }
    }
}
           
       

int main(){
    int i, j, t, l, tmp;
    scanf("%d\n", &t);
    while( t-- )
    {
        ans=0;
        tmp=0;
        gets(s);
        l=strlen(s);
        e=l-1;
        for( i=0; i<l; i++ )
        {
            if( s[i]==' ' )
                tmp++;
            if( tmp==2 )
            {
                st=i+1;
                break;
            }
        }
        st++; e--;
        DFS(st, e);
        printf("%d\n", ans);
    }
    return 0;
}



另外的題目

B應該是偏思考 可能沒有演算法在裡面 ..
(這種題是我罩門 直接交給隊友 隊友最後還是想不到瑕疵 超可惜的!)

E解法是爆搜(DFS)
清除次數不重要 因此可以..
轉換問題為保護m-k個點(<-爆搜這個)
看有哪幾行列不能清
看是不是有*號 行列(十字)皆不能清 (則此清法不可行)
我被題目的K害到了... for迴圈 ... - -+

[jurrasickill]

你的作法是錯的
這題沒那麼簡單 當初看到一開始以為是Greedy, 後來馬上找到反例
後來也想不到DP式

只是看到那麼多隊AC了大概就知道跟去年的迴文一樣用假解過就可以了...

給個容易錯的吧：
#define XXXX(x) (((x) * (x)) * (x))
你會輸出0
可是實際上前面因為已經是乘過的，所以後面的乘將前半段的括號拔除並不會有任何影響。
這是用*來看的，如果是從+來看的話
#define XXXX(x) (x + (x) * (x))
會因為+號後面有個括號你認為要拔掉，可是因為它相對應的括號(後面的乘前面那個) 被乘給綁住了，所以其實是不能拔的。

這題並沒有那麼容易...我們這隊有一個想法是直接把x代入兩個質數相加，多做幾次檢查。
還有另一隊好像是建樹，從外面慢慢往裡面剝。
這次這題跟去年pC都滿無言的QQ

[jurrasickill]

pB作法不少 我們AC的方法數就有三種@@
一種就純數學 另一種就二分搜答案 還有枚舉高度到根號N
只是總而言之的核心思想都是邊長固定的情況下，正方形的面積會是最大的。

而pE的話我是2^10枚舉打或不打來檢查囉~

[Nineguan]

我是用stack(有點像檸檬汽水那樣)
是隊友建議我往stack想
最後我也co出來了

[Nineguan]

給個容易錯的吧：
#define XXXX(x) (((x) * (x)) * (x))
你會輸出0
可是實際上前面因為已經是乘過的，所以後面的乘將前半段的括號拔除並不會有任何影響。

我的解法似乎也會錯這筆
code在隊友那裡所以我不知道

這是用*來看的，如果是從+來看的話
#define XXXX(x) (x + (x) * (x))
會因為+號後面有個括號你認為要拔掉，可是因為它相對應的括號(後面的乘前面那個) 被乘給綁住了，所以其實是不能拔的。

不過這筆我的code就有考慮到了XP所以這筆不會錯

[jurrasickill]

+很好處理阿~你只要記錄每筆相對應的括號就可以了
可是*你要一層一層剝...而且你還得考慮括號裡面是有沒有乘過的==

[Nineguan]

我大概知道怎麼處理
但是+的部分我沒有錯XP

我的co法大概就是遇到運算子或右括號時把stack裡匹配好的括號pop掉
(在push的時候有順便紀錄是否可以省略)
然後一一加到answer裡
我只push"(" , ")" , "+" , "*"
其餘空格&"x"省略掉

這樣處理應該只剩下剛剛說的 (((x) * (x)) * x) 會錯

[lini]

你的作法是錯的
這題沒那麼簡單 當初看到一開始以為是Greedy, 後來馬上找到反例
後來也想不到DP式

只是看到那麼多隊AC了大概就知道跟去年的迴文一樣用假解過就可以了...

給個容易錯的吧：
#define XXXX(x) (((x) * (x)) * (x))
你會輸出0
可是實際上前面因為已經是乘過的，所以後面的乘將前半段的括號拔除並不會有任何影響。
這是用*來看的，如果是從+來看的話
#define XXXX(x) (x + (x) * (x))
會因為+號後面有個括號你認為要拔掉，可是因為它相對應的括號(後面的乘前面那個) 被乘給綁住了，所以其實是不能拔的。

這題並沒有那麼容易...我們這隊有一個想法是直接把x代入兩個質數相加，多做幾次檢查。
還有另一隊好像是建樹，從外面慢慢往裡面剝。
這次這題跟去年pC都滿無言的QQ

噢 ...

我是從外後面往裡面剝沒錯 ...

題目我是跟著隊友的想法co ~ (他co不太出來 換我寫)

當下是有小小懷疑 本來也期待會return WA(看到AC從椅子上跳起來 ...)


可能DFS  還需要考慮回傳這一層括號裡面是不是全部乘法運算 .. ?

改天修一修 ... (我快睡著了 ...)


關於「#define XXXX(x) (x + (x) * (x))
會因為+號後面有個括號你認為要拔掉，可是因為它相對應的括號(後面的乘前面那個) 被乘給綁住了，所以其實是不能拔的。」
實測是輸出0 . ( 應該沒錯拔 ?

因為(x)右邊有*運算


我的隊友pB  也是做到sqrt(N)的樣子
可能想法有瑕疵 3WA

[Nineguan]

可是題目有說清楚(((x) * (x)) * (x))這種情形嗎
我的意思是說題目有說乘過了之後就可以拔括號了嗎?

[phat]

因為這題範圍很小

其實可以2^(括號對數)次方枚舉留下哪些括號

再用x = a + b * c + d    random選幾組a, b, c, d檢查是否和原本算式一樣

這樣有個保證正確的2^N * N的做法。

另外. 出題者表示可以做到O(N)

[Nineguan]

請問各位用堆疊法那樣複雜度是...?
我估計最多只會到2*n

[liouzhou_101]

根据phat所说的做法，将x替换为一个实际的表达式，然后再枚举去掉哪些括号。
只是本人的程式写得有些太麻烦了......

代碼: [選擇]

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<queue>

using namespace std;

string X="4+7";

char task[100];
string s,t;
int len,num,ans;
int pL[100],pR[100],mark[100],a[100];
long long v;

deque<int> Q;
deque<char> q,r;
long long st[100];

long long value(string s)
{
q.clear();
r.clear();
int len=s.length();
for (int i=0;i<len;++i)
{
if (s[i]=='(')
{
q.push_back(s[i]);
continue;
}
if (s[i]==')')
{
while (1)
{
char c=*q.rbegin();
if (c=='(') break;
r.push_back(c);
q.pop_back();
}
q.pop_back();
if (!q.empty())
if (*q.rbegin()=='*')
{
r.push_back('*');
q.pop_back();
}
continue;
}
if (s[i]>='0'&&s[i]<='9')
{
r.push_back(s[i]);
if (!q.empty())
if (*q.rbegin()=='*')
{
r.push_back('*');
q.pop_back();
}
continue;
}
if (s[i]=='+'||s[i]=='*')
{
q.push_back(s[i]);
if (q.size()>1)
if (*q.rbegin()=='+')
{
q.pop_back();
char c=*q.rbegin();
if (c=='+'||c=='*')
{
r.push_back(*q.rbegin());
q.pop_back();
}
q.push_back('+');
}
continue;
}
}
int tot=0;
for (deque<char>::iterator it=r.begin();it!=r.end();++it)
{
char c=*it;
if (c>='0'&&c<'9')
{
++tot;
st[tot]=c-48;
continue;
}
if (c=='+') st[tot-1]+=st[tot];
if (c=='*') st[tot-1]*=st[tot];
--tot;
}
return st[1];
}

void init()
{
cin>>task;
cin>>task;
getchar();
gets(task);
s.clear();
for (int i=0;i<strlen(task);++i)
{
if (task[i]=='x')
s+=X;
else if (task[i]!=' ')
s+=task[i];
}
v=value(s);
Q.clear();
len=s.length();
num=-1;
memset(mark,0,sizeof(mark));
for (int i=0;i<len;++i)
{
if (s[i]=='(')
{
++num;
pL[num]=i;
mark[i]=num;
Q.push_back(num);
}
if (s[i]==')')
{
pR[*Q.rbegin()]=i;
mark[i]=*Q.rbegin();
Q.pop_back();
}
}
}

bool check()
{
t.clear();
a[0]=0;
for (int i=0;i<len;++i)
if (!a[mark[i]])
t+=s[i];
int w=value(t);
return v==w;
}

void DFS(int x,int k)
{
if (ans<=k) return;
if (x>num)
{
if (check()) ans=k;
return;
}
a[x]=0;
DFS(x+1,k+1);
a[x]=1;
DFS(x+1,k);
}

void work()
{
ans=num;
DFS(1,0);
cout<<num-ans<<endl;
}

int main()
{
int T;
cin>>T;
while (T--)
{
init();
work();
}
return 0;
}


[sagit]

如果正解是 O(N), 那應該還是要用 stack 來做,
我是除了原本的 x 外, 又多兩種變數 y、z,
其中 y 是外面有一層括號, 但還不確定要不要拿掉,
像 (x) 就會變成 y,
而 z 是相乘之後得來的, 基本上不能再分解,
接下來把所有東西一一丟進 stack 裡, (註：我是直接把 + 丟掉)
遇到右括號 ) 再從 stack 裡一一拿出來直到遇到左括號 ( 為止,
然後把中間的東西轉換成 y 或 z 其中一個,
規則如下：

1.如果 ( ) 裡只有一個東西, (x) 會變成 y 再丟回去,
  (y)、(z) 則外面的括號可以去掉。
2.當 y、z 被丟回 stack 時, 如果頂端是 *,
  不管是 y*y、y*z、z*y、z*z 都會變成 z。
3.如果 ( ) 裡有兩個以上的東西, 則裡面所有的 y 的括號都可以去掉,
  而整個內容最後也會變成 y。
4.最後, 如果 stack 最後只剩下一個 y, 則可以再去掉一個 ( )
5.因為最後的 ( ) 一定要留下, 所以把去掉的 ( ) 數減一就是答案。

基本上應該是這樣, 不知道還有沒有沒考慮到的地方。

參考程式：(By sagit)

代碼: [選擇]

#include <cstdlib>
#include <iostream>

using namespace std;

char Stack[200], *p;
int top, cnt;

void Push(char c)
{
    if (c>='x'&&c<='z'&&top>=2&&Stack[top]=='*')
    {
        top-=2;
        Push('z');
    }
    else Stack[++top]=c;
}

int main()
{
    int t, i;
    char s[200], c;
    cin >> t;
    cin.getline(s, 200);
    while (t--)
    {
        cin.getline(s, 200);
        for (p=s; *p; p++)
            if (*p==')') break;
        for (p+=2, top=-1, cnt=0; *p; p++)
        {
            c=*p;
            switch (c)
            {
                case '(':
                case 'x':
                case '*':
                    Push(c);
                    break;
                case ')':
                    if (Stack[top-1]=='(')
                    {
                        switch(Stack[top])
                        {
                            case 'x':
                                top-=2;
                                Push('y');
                                break;
                            case 'y':
                                top-=2;
                                cnt++;
                                Push('y');
                                break;
                            case 'z':
                                top-=2;
                                cnt++;
                                Push('z');
                                break;
                        }
                    }
                    else
                    {
                        for (i=top; Stack[i]!='('; i--)
                            if (Stack[i]=='y') cnt++;
                        top=i-1;
                        Push('y');
                    }
                    break;
            }
        }
        if (top==0&&Stack[0]=='y') cnt++;
        cout << cnt-1 << endl;
    }
    return 0;
}

[hsieang]

看到這題我的直覺居然是導公式...

代碼: [選擇]

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int T,l,sum,n,m,k;
string s;
char x;
while(cin>>T)
{
getline(cin,s);
while(T--)
{
getline(cin,s);
l=s.size();
sum=0;
n=0;
m=0;
k=0;
x='A';
for(int i=0;i<l;i++)
{
if(s[i]=='(') sum++;
if(s[i]=='*')
{
if(x=='*')
{
m++;
}
n++;
x='*';
}
if(s[i]=='+')
{
x='+';
if(s[i-2]==')'&&s[i+2]!='(') k++;
}

}
sum=sum-2;
if(n<=1) cout<<sum-2*n<<endl;
else cout<<sum-(2*n-m)+k<<endl;
}
}
}

[hsieang]

是我想的太簡單嗎OAO
測資丟上自架OJ是對的
我的做法：計算有幾個括號(不含最外面)，因為乘法例如a*b則a和b都需要括號，所以減掉2，但若是連乘例如a*b*c，則括號只有第一個是兩個，後面都只需要一個，最後輸出剩下的括號數

代碼: [選擇]

#include<iostream>
#include<cstring>
using namespace std;
int main(){
   int T;
   string s;
   cin>>T;
   while(T--){
      cin>>s>>s;
      getline(cin,s);
      int len = s.length(), count=0;
      char before = '+';
      for(int i=2;i<len-1;i++){
         if(s=='(') count++;
         else if(s=='*'){
            count-=2;
            if(before == '*') count++;
            before = '*';
         }
      }
      cout<<count<<endl;
   }
}