#include<stdio.h>
#include<string.h>
int main()
{
   int n,t,count,i;
   static int a[1000000];
   char b[7];
   scanf("%d%d",&n,&t);
   while(t--)
   {
     scanf("%s",b);
     if(!strcmp(b,"CHANGE"))
     {
       scanf("%d",&count);
       if(a[count]==0)
         a[count]=1;
       else
         a[count]=0;
       continue;
     }
     count=0;
     if(!strcmp(b,"QUERY"))
     {
       for(i=1;i<=n;i++)
         if(a[i]==1)
          count++;
       printf("%d\n",count);
     }
   }
   return 0;
}
********************************
**************************************
**********************************************
描述
灯光师小明控制着各种晚会的各种大小灯，每次晚会小明都会对灯进行很多次操作。对每盏灯只能进行两种操作，开和关。现在小明希望自己随时都知道还有多少盏灯亮着。你需要编写一个程序当小明问你时你能快速的说出还有多少盏灯亮着，晚会开始时所有的灯都是灭的。
输入
只有一组数据第一行输入两个正整数N，T（0<N<=100000,0<T<=1000000）N表示有N盏灯，T表示有T条指令。随后T行每行有一条指令，这条指令包含一个字符串，当字符串为CHANGE，它后面还有一个整数m，表示对第m盏灯进行一次操作(操作表示如果第m盏灯灯是开着时就关闭，如果灯是关着时就打开)。当字符串为QUERY，表示小明想查询现在还有多少盏灯亮着。
输出
每次查询指令输出占一行，输出当前亮着灯的个数
样例输入
10 8
CHANGE 1
QUERY
CHANGE 2
QUERY
CHANGE 1
CHANGE 9
CHANGE 7
QUERY样例输出
1
2
3

提交代码oj显示时间太长，无法提交。各位大侠有没有更好的思路分享一下？？？？

关变开，答案+1，否则减1

那也快不多少，有没有其他的有效减少时间的思路。

1.首先有一个建议，字符串比较可以改成判断字符串的第一个字母，这样应该会加快不少。

2.楼上的建议是一个非常好的建议！你的代码最大时间消耗就在于每次Query时，重新计算灯亮的个数，这是O(N*T)的时间消耗；
如果改成每次计算countx则是O(T)的时间复杂度。你自己想想吧。

3.另外你比较了"CHANGE"这个字符串之后，完全没有必要再比较是否等于"QUERY"，这是必然的。

PS：楼上是个高手！

[ 本帖最后由 CrystalFan 于 2012-1-4 19:30 编辑 ]

#include<stdio.h>
#include<string.h>
int main()
{
   int n,t,count,i,countx=0; //初始化计数器
   static int a[1000000];
   char b[7];
   scanf("%d%d",&n,&t);
   while(t--)
   {
     scanf("%s",b);
     if(b[0]=='C')  //判定"CHANGE"直接用首字母比较
     {
       scanf("%d",&count);
       if(a[count]==0)
             {
                 countx++; //开灯则计数加1
                 a[count]=1;
             }
       else
             {
                 countx--; //关灯则计数减1
                 a[count]=0;
             }
       continue;
     }
     //无需再判定是否是"QUERY"
     printf("%d\n",countx);
   }
   return 0;
}

按你的改的

[ 本帖最后由 CrystalFan 于 2012-1-4 20:46 编辑 ]

谢谢两位大侠。

还有没有人发表意见，明天我再结贴。

楼主的问题很简单，楼上两位的回答也已经没有补充的必要了。

跟贴的原因是楼主的问题让我想起了另一个有趣的游戏，楼主以及各位如果感兴趣可以考虑一下。

那个游戏也是点灯，不过是一个N行M列的灯阵。
每盏灯也只有两个状态，亮或灭。
对一盏灯的操作除了会改变这盏灯的状态外，还会改变与它相邻的上下左右的灯的状态。

现在的问题是，初始灯阵是全灭的，有没有可能把所有的灯都点亮？如果可能，则最少需要多少步？给出操作的过程。
这个问题还可以扩展一下，给定一个灯阵的初始状态，能不能变换到另一个给定的状态？

各位可以先在纸上试一下3 X 3的灯阵

这。。前几天我通宵复习生化的时候在ubuntu下玩那个点灯游戏的时候刚好想过这个问题

首先每个灯要么不按，要么按一次，因为按多次(n次,n>=2)时是等价于n%2次的

这个时候我们相当于有n*m个未知数，对应同样数目的方程，比如n=m=3时，(2,2)这个点所对应的方程就是x(1,2) xor x(2,1) xor x(2,2) xor x(2,3) xor x(3,2)=1

n*m个方程列出来然后求解，这个我没试过，应该和高斯消元法是类似的，这个题目有什么OJ有的吗？

我也没见过这样的OJ。很久以前在另一个论坛有人提出，当时我给出了完整的证明，好像还写了一段代码，刚才找了一下没找到。
如你所言，解一个线性方程组即可。好像见过些益智小游戏也是类似的玩法。